  We study the evolution of the star formation rate (SFR) - stellar mass
(M_star) relation and specific star formation rate (sSFR) of star forming
galaxies (SFGs) since a redshift z~5.5 using 2435 (4531) galaxies with highly
reliable (reliable) spectroscopic redshifts in the VIMOS Ultra-Deep Survey
(VUDS). It is the first time that these relations can be followed over such a
large redshift range from a single homogeneously selected sample of galaxies
with spectroscopic redshifts. The log(SFR) - log(M_star) relation for SFGs
remains roughly linear all the way up to z=5 but the SFR steadily increases at
fixed mass with increasing redshift. We find that for stellar masses M_star>3.2
x 10^9 M_sun the SFR increases by a factor ~13 between z=0.4 and z=2.3. We
extend this relation up to z=5, finding an additional increase in SFR by a
factor 1.7 from z=2.3 to z=4.8 for masses M_star > 10^10 M_sun. We observe a
turn-off in the SFR-M_star relation at the highest mass end up to a redshift
z~3.5. We interpret this turn-off as the signature of a strong on-going
quenching mechanism and rapid mass growth. The sSFR increases strongly up to
z~2 but it grows much less rapidly in 2<z<5. We find that the shape of the sSFR
evolution is not well reproduced by cold gas accretion-driven models or the
latest hydrodynamical models. Below z~2 these models have a flatter evolution
(1+z)^{Phi} with Phi=2-2.25 compared to the data which evolves more rapidly
with Phi=2.8+-0.2. Above z~2, the reverse is happening with the data evolving
more slowly with Phi=1.2+-0.1. The observed sSFR evolution over a large
redshift range 0<z<5 and our finding of a non linear main sequence at high mass
both indicate that the evolution of SFR and M_star is not solely driven by gas
accretion. The results presented in this paper emphasize the need to invoke a
more complex mix of physical processes {abridge}
