We investigate the non-equilibrium electronic structure and characteristic time scales in a candidate excitonic insulator, Ta$_2$NiSe$_5$, using time- and angle-resolved photoemission spectroscopy with a temporal resolution of 50 fs. Following a strong photoexcitation, the band gap closes transiently within 100 fs, i.e., on a time scale faster than the typical lattice vibrational period. Furthermore, we find that the characteristic time associated with the rise of the photoemission intensity above the Fermi energy decreases with increasing excitation strength, while the relaxation time of the electron population towards equilibrium shows an opposite behaviour. We argue that these experimental observations can be consistently explained by an excitonic origin of the band gap in the material. The excitonic picture is supported by microscopic calculations based on the non-equilibrium Greens function formalism for an interacting two-band system. We interpret the speedup of the rise time with fluence in terms of an enhanced scattering probability between photo-excited electrons and excitons, leading to an initially faster decay of the order parameter. We show that the inclusion of electron-phonon coupling at a semi-classical level changes only the quantitative aspects of the proposed dynamics, while the qualitative features remain the same. The experimental observations and microscopic calculations allow us to develop a simple and intuitive phenomenological model that captures the main dynamics after photoexcitation in Ta$_2$NiSe$_5$.