How are you generating the NavMesh (dynamically at runtime or statically)? If your terrain will remain static, you may want to seek a way to store the mesh data in a file so you can quickly load it back up. Perhaps GetNavigationDataAttr/SetNavigationDataAttr would allow you to load the vertex data. I'm new to NavMesh, so this advice my be incorrect, but that's how I would initially approach the problem.
If you're creating a procedural world however, you may have to be more clever. Splitting the world into parts/chunks might be best; then generate the navmesh for each part dynamically in a background thread.