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 similar or equal to 5.5 using 2435 (4531) galaxies with highly 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 \textgreater= 3.2 x 10(9) M-circle dot the SFR increases by a factor of similar to 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 of 1.7 from z = 2.3 to z = 4.8 for masses M-star = 1010 M-circle dot. We observe a turn-off in the SFR-M-star relation at the highest mass end up to a redshift z similar to 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 similar to 2, but it grows much less rapidly in 2 \textless z \textless 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 similar to 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 similar to 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 \textless z \textless 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 including major and minor merging to further understand the co-evolution of the SFR and stellar mass growth.