While watching Naruto, I had this same question,
And one of the conclusions I came up with was also the conclusion of the accepted answer:
As you can see, the village is quite large. I can estimate a population of over 100,000 easily. Since many of them are shinobi, I don't think it's exaggerated to think that there are at least 12,000 shinobi there (probably more).
(I think the wikia stated somewhere that it has around 80,000 persons, so I thought may be the thousands of ninjas actually came from there)
But that doesnt explain very well why was Tsunade always short of ninjas for the missions. How is this explained? Is there an elite of ninjas that can only be chosen for missions, are the rest of ninjas from the land of fire in the 4th shinobi war actually coming from other villages in the land of fire or what?
If there are thousands of ninjas in Konoha, why was Tsunade always short of ninjas for the missions in the anime?