Sometimes the DM has to take clear and obvious shortcuts but just have fun with them.
Like in the "He who fights with monsters" books. Theres a bunch of largely unimportant recurring npc characters. So the author made them Octuplets. Albert, Bertram, Gilbert, Herbert, Philbert, Hubert, Robert, and Bertrand. The best thing about the brothers Bertinelli is that they all respond to "Bert".
When I start work on a new setting and have a rough general idea of the cultures that will inhabit it, I pick countries that I think are somewhat culturally comparable and look up lists with common names from those countries. Then I make myself a big list of names that I think sound like decent names for characters in my setting and copy them all into one big list of NPC names sorted by culture. If I need an NPC name later, I can go to that list. If nothing on the list seems fitting, I at least have a good pool of references for the sounds and letters that are common for that culture and can make up names that sound similar to the actually existing ones.
I usually take a look at names from one language and choose those I like the most. Recently I held the game in another random fantasy world where PCs were new and I made sure my players don't have a lot to do with French and gave every NPC a French name. But they can be hard to pronounce and to note by players if you don't know it.
Good picks are Nordic names - Norwegian/Danish/Swedish - because of popcultural references. I'm thinking of making repository of semi-Polish fantasy names for all those who like Slavic themes but there is a long way before me.
I think names are surprisingly important — they establish the atmosphere of your world just like background music sets the tone of a film.
I generate random words using an online tool (recently I've been using donjon.bin.sh). For my world, the fantasy names are too "tropey", so I use the Markov Chains generator (Markov Chains use source text to structure the random syllables it generates—if your source text has no Zs, nor will your random words).
In general (but not always) I figure that short, one syllable names are most suitable for nicknames, or for common, lower class names. Two syllable names tend to be typical, ordinary people, three syllable names are more well-to-do, four syllables names are more high-class (or pretentious) and five or more syllable names are very exotic—probably foreign dignitaries, wizards or sages. (They'll probably have shorter names that friends actually know them by—if they have friends!)
Place names are just as important—in fact, even more important! Often place names contribute to someone's name, or a historic person's name can become the name of a place.
Similarly, the names of Gods and Goddesses are vital. Get them wrong, and it'll skew the whole vibe of your setting.
If you like, you can get creative, and make name words for particular regions have a particular character. Grab a source text for your Markov Chains that has the forms "kn" and "gn" in a lot. Okay, that's one particular area. Use the combos "dz" and "dj" for another area.
Maybe have one area where everyone who's male has a name ending in o, and everyone who's female has a name ending in a. And, of course, the residents of that area will add o or a to the characters' names—because that's the rule for names!
When the PCs meet someone then they should, eventually, be able to guess their approximate social status, the region their family comes from, their religion, and maybe even their current place of residence—just from their name!
And yes. People's names can change over time! Part of them will stay the same, but part may be to do with their profession, their home or something they're famous for.
I tend to find my "hit rate" on suitable names is only about 2%. Most random words aren't easily pronouncable, or just don't feel right. So sometimes I'll spend a half hour just generating names and saving them off in a list. I don't know what the names are for yet, I just have them on the side, then slot them into game sessions as appropriate. Yeah. I almost never use more than 25% of my name lists. So I generate more!
And pro-tip: some regions may have default names. In medieval England, loads of people were just called John—meaning, "You! Unimportant person!". John Smith, John Miller, John Farmer, John Wheelwright… And even if that wasn't their actual name, if that's what his Lordship calls you, who are you to argue?
Go to a baby names site, pick a relevant culture to match your game's territory, pick names.