No debes hacerla con frames.
Los frames son molestos, y dan problemas con el botón atrás y adelante, además de que no son buenos para posicionarte en los buscadores.
La solución es fácil, si tienes un hosting con PHP, usa este includes para meter el menú:
Código PHP:
<?php include('url/del_archivo.php'); ?>
Que lo que hará será "pegar" el código del archivo en cuestión en ese lugar.