We present measurements of black hole masses and Eddington ratios ({lambda}_Edd_) for a sample of 38 bright (M_1450_<-24.4mag) quasars at 5.8<~z<~7.5, derived from Very Large Telescope/X-shooter near-IR spectroscopy of their broad CIV and MgII emission lines. The black hole masses (on average, M_BH_~4.6x10^9^M_{sun}_) and accretion rates (0.1<~{lambda}_Edd_<~1.0) are broadly consistent with that of similarly luminous 0.3<~z<~2.3 quasars, but there is evidence for a mild increase in the Eddington ratio above z>~6. Combined with deep Atacama Large Millimeter/submillimeter Array (ALMA) observations of the [CII]158um 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>~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~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~0 galaxies. These results paint a picture where the first supermassive black holes reside in massive halos at z>~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.