1- Overload the getMenu method of your controller and use custom SQL to fetch only the columns you need. Or write a new function like getSimpleMenu (probably a better idea).
3- Use partial or total caching, read:
Method #1 is not terrible and you can do it along side #3 for even better performance. Method #2 is a bad idea in that it requires a lot of effort and any gains come at the expense of breaching the mvc model. #3 is quicker to implement and will likely give the largest performance boost on average.
In this instance you would wrap your menu with this:
<% cached 'navigation', List(Page).max(LastEdited) %> ***
<% cached 'navigation', Aggregate(Page).Max(LastEdited) %>
<% end_cached %>
*** The struck out line is for 3.0, my bad.
Now I haven't tried this, but according to the page at the link I posted, the section wrapped in this will be cached until any page on the site is edited. So if after you are done making edits you refresh a page on your site with the navigation, your visitors will always get a cached copy of the menu.
Alternatively you can cache entire pages. You can read up on that here: