Via amplification by turbulent dynamo, magnetic fields can be potentially important for the formation of the first stars. To examine the dynamo behavior during the gravitational collapse of primordial gas, we extend the theory of nonlinear turbulent dynamo to include the effect of gravitational compression. The relative importance between dynamo and compression varies during contraction, with the transition from dynamo- to compression-dominated amplification of magnetic fields with the increase of density. In the nonlinear stage of magnetic field amplification with the scale-by-scale energy equipartition between turbulence and magnetic fields, reconnection diffusion of magnetic fields in ideal magnetohydrodynamic (MHD) turbulence becomes important. It causes the violation of flux-freezing condition and accounts for (a) the small growth rate of nonlinear dynamo, (b) the weak dependence of magnetic energy on density during contraction, (c) the saturated magnetic energy, and (d) the large correlation length of magnetic fields. The resulting magnetic field structure and the scaling of magnetic field strength with density are radically different from the expectations of flux-freezing.