In a multiwavelength survey of 13 quasars at 5.8 ≲ z ≲ 6.5, which were preselected to be potentially young, we find five objects with extremely small proximity zone sizes that may imply UV-luminous quasar lifetimes of ≲100,000 yr. Proximity zones are regions of enhanced transmitted flux in the vicinity of quasars that are sensitive to the quasars' lifetimes because the intergalactic gas has a finite response time to their radiation. We combine submillimeter observations from the Atacama Large Millimetre Array and the NOrthern Extended Millimeter Array, as well as deep optical and near-infrared spectra from the medium-resolution spectrograph on the Very Large Telescope and on the Keck telescopes, in order to identify and characterize these new young quasars, which provide valuable clues about the accretion behavior of supermassive black holes in the early universe and pose challenges on current black hole formation models to explain the rapid formation of billion-solar-mass black holes. We measure the quasars' systemic redshifts, black hole masses, Eddington ratios, emission-line luminosities, and star formation rates of their host galaxies. Combined with previous results, we estimate the fraction of young objects within the high-redshift quasar population at large to be 5% ≲ f young ≲ 10%. One of the young objects, PSO J158-14, shows a very bright dust continuum flux (F cont = 3.46 0.02 mJy), indicating a highly starbursting host galaxy with a star formation rate of approximately 1420 M o˙ yr-1.