Hooking into the init action will fire it too frequently?

It really depends on your situation. Whenever you add a rewrite rule and flush the permalinks, it will stay there till the next change/flush of the permalink’s settings.

If it’s vital for your rules to exist, you can check if it exists on init, and then add it if it’s not there. Take a look at this answer to get a glimpse of how to check if a rewrite rule exists.

If it’s not really necessary for your rules to exist ( for example, you are just doing it for SEO purpose ), you can hook into another action that doesn’t run each time a page loads, such as plugin activation.