Not very long at all.
Ollivander makes Luna Lovegood a new wand in a matter of weeks in Deathly Hallows.
Mr Ollivander had sent Luna a new wand that morning. She was out on the back lawn at that moment, testing its capabilities in the late afternoon sun.
(Deathly Hallows, Chapter 26, Gringotts).
This occurs the day before the raid on Gringotts. Based on the dates which JKR uses in the documentary J.K. Rowling: A Year in the Life, the Battle of Hogwarts took place on 2nd May 1998. This is backed up by her tweets - she has taken to tweeting on 2nd May each year to apologise for killing off characters in the battle. Using this timeline, the Gringotts break-in took place on 1st May and Luna received her new wand on 30th April.
Ollivander can't have started making the wand until after he left Shell Cottage. Unfortunately, we don't know when exactly this was. However, it can't have taken him more than a month. We know that it was already April by the time he left.
"I'm sorry," he told Fleur, one blustery April evening as he helped her prepare dinner. "I never meant for you to have to deal with all this."
(Deathly Hallows, Chapter 25, The Wandmaker).
So making her wand could've taken him a couple of hours or it could've taken him several weeks. But it took him no more than one month.
I would expect him to be able to produce more than one wand a month. As the question says, he owns thousands of wands at any given moment. Given that he sells hundreds of wands every year he must be able to make a dozen or so every month to make sure his supplies don't get depleted. Although, as Jeremy French says, some of the wands may have been on the shelves for a very long time.