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}