Just like you did in your current code, you could simply list all your links with <br> separating them. There are higher-tech ways to do it, but that's unrelated to this particular discussion. So then you have a list of your nav items, and you put it all in one file, called nav.inc or so. It essentially looks like the code I gave you, but again it should be stripped of all the doctype, head, body, etc stuff.
Then in each of your site pages, you'd have a line like:
<?php include ("nav.inc"); ?>
wherever you want the nav included (ie, probably a <div> on the left side of the page).
That should do it.