A quick check of Wikipedia's Helium-3 introduction says:
The abundance of helium-3 is thought to be greater on the Moon than on Earth, having been embedded in the upper layer of regolith by the solar wind over billions of years, though still lower in abundance than in the solar system's gas giants.
but let's not assume that Wikipedia is the last word on the topic.
According to NASA's Elemental and Isotopic Abundances in the Solar Wind; An invited review by Johannes Geiss:
Apollo 11 Apollo 12
flux in cm^-2 sec^-1
He4 - Flux 6.2 +/- 1.2 × 10^6 8.1 +/- 1.0 × 10^6
He3 - Flux 3.3 +/- 0.7 × 10^3 3.3 +/- 0.4 × 10^3
3300 atoms/sec/cm^2 is 0.0005 mole/sec over the Moon's surface, which is about 16,000 moles/year or about 49 kg/year.
According to the abstract of Global inventory of Helium-3 in lunar regoliths estimated by a multi-channel microwave radiometer on the Chang-E 1 lunar satellite:
The global inventory of 3He was estimated as being 6.6×10⁸ kg; 3.7×10⁸ kg for the lunar nearside and 2.9×10⁸ kg (660 million kilograms) for the lunar farside.
At a rate of 49 kg/year assuming 100% capture efficiency, it would take about 13 million years to reach a total of 6.6×10⁸ kg. A nominal solar wind velocity of order 100 km/sec for example corresponds to a helium-3 kinetic energy of about 50 eV, so we can think of the captured atoms as being "implanted" a few nanometers or more down into whatever surface it first hits, which is a fairly shallow and delicate location for a noble gas atom.
Therefore, thinking that it would only take of the order of 13 million years to replenish the Moon's helium-3 would be naive because there are several competing processes. The far higher flux of protons in the solar wind, cosmic rays, and micrometeorites all can disturb the regolith and release trapped noble gasses like helium, and atoms with escape velocity can return to space.
So the answer is probably between tens of millions and the canonical, Sagan-esque "billions" of years.