Over the past decade, the existence of a substantial population of opticallyinvisible, massive galaxies at $z\gtrsim3$ has been implied from mid-infraredto millimeter observations. With the unprecedented sensitivity of the JWST,such extremely massive galaxy candidates have immediately been identified evenat $z>7$, in much larger numbers than expected. These discoveries raised a hotdebate. If confirmed, early, high-mass galaxies challenge the current models ofgalaxy formation. However, the lack of spectroscopic confirmations leads touncertain stellar mass ($M_{\star}$) estimates, and the possible presence ofactive galactic nuclei (AGN) adds further uncertainty. Here, we present thefirst sample of 36 dust-obscured galaxies with robust spectroscopic redshiftsat $z_{\rm spec}=5-9$ from the JWST FRESCO survey. The three most extremesources at $z\sim5-6$ ($\sim$1 billion years after the Big Bang) are so massive(log$M_{\star}/M_{\odot}$ $\gtrsim11.0$) that they would require, on average,about 50% of the baryons in their halos to be converted into stars -- two tothree times higher than even the most efficient galaxies at later times. Theextended emission of these galaxies suggests limited contribution by AGN. Thispopulation of ultra-massive galaxies accounts for 20% of the total cosmic starformation rate density at $z\sim5-6$, suggesting a substantial proportion ofextremely efficient star formation in the early Universe.