We present the star formation rate-stellar mass (SFR-M*) relation for galaxies in the Cosmic Evolution Early Release Science survey at 4.5 ≤ z ≤ 12. We model the JWST and Hubble Space Telescope rest-UV and rest-optical photometry of galaxies with flexible star formation histories (SFHs) using BAGPIPES. We consider SFRs averaged from the SFHs over 10 Myr (SFR10) and 100 Myr (SFR100), where the photometry probes SFRs on these timescales, effectively tracing nebular emission lines in the rest-optical (on ~10 Myr timescales) and the UV/optical continuum (on ~100 Myr timescales). We measure the slope, normalization and intrinsic scatter of the SFR-M* relation, taking into account the uncertainty and the covariance of galaxy SFRs and M*. From z ~ 5 to 9 there is larger scatter in the SFR10-M* relation, with σ ( log S F R 100 ) = 0.4 dex, compared to the SFR100-M* relation, with σ ( log S F R 10 ) = 0.1 dex. This scatter increases with redshift and increasing stellar mass, at least out to z ~ 7. These results can be explained if galaxies at higher redshift experience an increase in star formation variability and form primarily in short, active periods, followed by a lull in star formation (i.e., “napping” phases). We see a significant trend in the ratio RSFR = SFR10/SFR100 in which, on average, RSFR decreases with increasing stellar mass and increasing redshift. This yields a star formation “duty cycle” of ~40% for galaxies with log M * / M ⊙ ≥ 9.3 at z ~ 5, declining to ~20% at z ~ 9. Galaxies also experience longer lulls in star formation at higher redshift and at higher stellar mass, such that galaxies transition from periods of higher SFR variability at z ≳ 6 to smoother SFR evolution at z ≲ 4.5.