My memory of this is sketchy and I hope I don't jumble it too much. I read two or three books (possibly more exist) in a series in the late 1990s. The whole thing was mainly SF with a dose of fantasy.
The main character is a man who is immortal. He doesn't age and can recover from even the most horrific wounds. I'm not sure if there where other immortals (I seem to recall a woman and another man). As far as I can recall, immortals were infertile and couldn't have children.
He lives among a tribe of nomadic people who roam the prairies of post-apocalyptic North America on horseback (society like Native American prairie tribes). Among their tribes (there is more than one) also live huge (lion-sized?) cats who are telepathic and have near-human level intelligence. The immortal man is a leader among the nomads and, I seem to recall, he is instrumental in getting the tribes together in a larger alliance and gradually moving them East to the coast.
On the east coast, some cities remain (Pittsburgh I clearly recall) who have a medieval feudal society with a militia and knight-based military. (I clearly remember that military ranks among them had Greek-derived names, which was quite strange.)
There was also a small group of people who had retained pre-apocalypse technology (radios, trucks, helicopters, firearms), possibly survivors or descendants of the military or of some scientists. These people were antagonistic to the immortal and try to kill or capture him. The immortal had some narrow escapes. They mainly work in secret and avoid letting their presence be known among the tribes.