We present measurements of black hole masses and Eddington ratios (lambda (Edd)) for a sample of 38 bright (M (1450) < -24.4 mag) quasars at 5.8 less than or similar to z less than or similar to 7.5, derived from Very Large Telescope/X-shooter near-IR spectroscopy of their broad C iv and Mg ii emission lines. The black hole masses (on average, M (BH) similar to 4.6 x 10(9) M (circle dot)) and accretion rates (0.1 less than or similar to lambda (Edd) less than or similar to 1.0) are broadly consistent with that of similarly luminous 0.3 less than or similar to z less than or similar to 2.3 quasars, but there is evidence for a mild increase in the Eddington ratio above z greater than or similar to 6. Combined with deep Atacama Large Millimeter/submillimeter Array (ALMA) observations of the [C II] 158 mu m line from the host galaxies and VLT/MUSE investigations of the extended Ly alpha halos, this study provides fundamental clues to models of the formation and growth of the first massive galaxies and black holes. Compared to local scaling relations, z greater than or similar to 5.7 black holes appear to be over-massive relative to their hosts, with accretion properties that do not change with host galaxy morphologies. Assuming that the kinematics of the T similar to 10(4) K gas, traced by the extended Ly alpha halos, are dominated by the gravitational potential of the dark matter halo, we observe a similar relation between black hole mass and circular velocity as reported for z similar to 0 galaxies. These results paint a picture where the first supermassive black holes reside in massive halos at z greater than or similar to 6 and lead the first stages of galaxy formation by rapidly growing in mass with a duty cycle of order unity. The duty cycle needs to drastically drop toward lower redshifts, while the host galaxies continue forming stars at a rate of hundreds of solar masses per year, sustained by the large reservoirs of cool gas surrounding them.