That's an interesting concept. Not quite sure if I like it, but it would certainly have some really cool effects. Like when that peaceful leader you built a relationship with suddenly gets replaced with an ****** that starts marching their armies against you.
The main problem I see with this is that most Civilizations only exist(ed) during a relatively short period of time. It wouldn't quite make sense to replace the leader of an ancient Civilization during the medieval ages, so that mechanic would be very inconsistent among Civilizations.
Factual time period of their rule isn't significantly important. There's a leader pool for every nation, guess Huns would have only 1 leader, but for most it isn't difficult at all to come up with many more. The order they appear in is not important, and would be randomized.
This could really work and be a lot of fun for players.
Example: You play a game of CVI
Your empire has 4 continental neigbours: England, Egypt, Russia and Rome.
England/Britain start with Elizabeth who eventually gets replaced by Victoria followed by Henry VIII only to be replaced by Churchill in more modern eras.
Egypt at the start of the game is ruled by Nefertiti, at the start of the Classical era Ramesses II takes over(much more aggressive leader) only to hand power to Hatshepsut who in turn hands the reins to Cleopatra.
For Russia you might draw Ivan the terrible as the first leader(likely a war situation) but then slightly less aggressive Nicholas II(or rather Peter the Great) takes over in classical era, followed by Catherine in Medieval and Lenin in later stages.
Your last continental neighbour, the Romans, are ruled by Augustus, followed by Julius Caesar, later perhaps by Marcus Aurelius and Hadrian.
All of those leaders are different and with their replacement your empire could expect more cooperation, trade or even a lasting alliance, or war over territory and resource might start, espionage, perhaps a cold war.
What would be cool is having some of the rulers change their personalities upon acquiring new social policy or tech discoveries (especially militaristic and spiritual type ones).
For example:
The young Ashoka of India (more exactly Maurya), was at younger age a very militaristic and aggressive ruler.
However, he changed his personality/traits dramatically after he converted to Buddhism and became a pacifistic ruler.
So perhaps until Ashoka(Asoka) converts his empire to one of the Monotheistic religions he, and thus India, could be a very aggressive neighbor but thereafter a docile and friendly civ (especially if converting to Buddhism)