We develop a theory of the valley Hall effect in high-quality graphene samples, in which strain fluctuation-induced random gauge potentials have been suggested as the dominant source of disorder. We find a near-quantized value of valley Hall conductivity in the band transport regime, which originates from an enhanced side jump of a Dirac electron when it scatters off the gauge potential. By assuming a small residue charge density our theory reproduces qualitatively the temperature- and gap-dependence of the observed valley Hall effect at the charge neutral point. Our study suggests that the valley Hall effect in graphene systems represents a new paradigm for the anomalous Hall physics where gauge disorder plays an important role.