I think GitHub Pages only supports a whitelist of plugins, so you might have some more difficulties solving it well without any plugins. I use Netlify for my site, which does support arbitrary plugins.

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