We parse sitenav.xml and all other nav xml files on each page, and sometimes multiple times per page. This is bad, fix it.
This turned out to be database accesses that were slowing things down, not sitenav.