Add a php include to each page referencing a single, common file that has the links and nav code in it. You don't even need to change the extensions of your pages, they can stay .htm or .html or whatever. The only thing you'll need to do is to add an .htaccess file to tell the server root or directory so it'll parse .htm pages as PHP, like this:
AddType application/x-httpd-php .php .htm .html
You can make a change in the common file and all the pages will reflect the change immediately.