init is the recommended hook and no, the rewrite rules will not be overwritten each time the hook fires or that the page is loaded, unless if you call flush_rewrite_rules() or WP_Rewrite::flush_rules() in your callback.
add_action( 'init', 'add_my_rewrite_rules' );
function add_my_rewrite_rules() {
add_rewrite_rule( ... );
flush_rewrite_rules(); // don't do this
}
So please don’t do that, or do it only upon plugin/theme activation and deactivation — and if you don’t already know, you can easily flush the rules by simply going to the Permalink settings admin page, without having to hit the Save Changes button.