and continuing it into the next life.
I imagine, the next life might be a good place to delve into the ideas you had earlier, like him wanting to learn magic like the witch, or the empire wanting to cover up local history.
The story stresses thoroughly that they have a racial/species difference with all the "human" references, but it might be fun to establish a different basis for their different life spans. Why does she think she has to be alone, and nature dictates that he leaves her that way? It seems she didn't grasp the possibilities when he reincarnated and showed up again.
You could introduce her teacher, who explained their fate as racial, but maybe it was a kind deception. Maybe her people sought to preserve their young with magic that sacrificed their fertility for longevity and altered their appearance as a side-effect, like in the Witcher series. Or, maybe it involved some other kind of sacrifice, such as needing to remember as in The Giver (not really an immortality story, but it lines up with your idea of remembering lost history).
Alternatively, maybe time moves differently for her, such that she is present when others remember her and seek her out, but maybe she kind of runs on autopilot between major plot points, like the MC in Click or like this manga with its massive time jumps between chapters. In all of these scenarios, it may be wonderful for her to teach him magic and learn through that experience about what it's like to live in many more moments and maybe untangle mysteries of her life and people as well.