Neat, thanks for noticing, the theme is basically a slightly simplified version of https://github.com/just-the-docs/just-the-docs, never suspected it was an issue with it, I'll take a look to see what can I fix!
One quick way to make it faster is to include that "_includes/nav.html" only in a nav.html, and then use an iframe to load that on every page, or something like that.
Anyway, I'm not the first to notice this it seems, although even "twice as fast" would still be quite slow: https://github.com/just-the-docs/just-the-docs/issues/1323