Well, if your navigation proc is running db queries, of course it's going to slow the page down more than a simple "here, use this style sheet" sort of proc.
Depending on what it is generating, you could try caching parts or all of it. But it shouldn't be surprising that as you make your server do more, it will take longer.
