Getting National Heroes - How Long?

[Saxon]

The luck level directly effects the chances of a hero showing up. I remember being surprised at how big an effect it had, but regret I do not remember the exact details. However, if you boost your luck up, you really should be getting them early in play, early enough to count on it. It is a bit unpredictable, but when you boost it, you will get results. You might want to do a search for the details.

It can really help if you get the national hero with high summoning skill for Rhyleh, though I never found out if the luck scales effected the chances of summoning.