Before I begin, I should note during the Warring States, there was at least one province ruled by ninjas (kinda):
https://en.wikipedia.org/wiki/Iga_ikki
But the thing with ninja is, in a quasi-Sengoku setting like Naruto were, ninja were among the lowest type of people around. But by Shippuden, things like that merchant who hired the team for his bridge was a total afterthought, it became a world of ninja and nothing but them.