NopCommerce made strange decision for 3.x to load subcategories only of active category and make separate cache for every single category. Reason for this move was to increase performance by preventing loading of thousands of categories from database with single request. This of course doesn't make much sense for say hundreds of categories, it actually makes browsing store with expiring cache slower.
Load all categories fix
To load all categories including sub-categories you have to change method PrepareCategoryNavigationModel in \Presentation\Nop.Web\Controllers\CatalogController.cs around line 218
for (int i = 0; i <= breadCrumbIds.Count - 1; i++)
if (breadCrumbIds[i] == category.Id)
categoryModel.SubCategories.AddRange(PrepareCategoryNavigationModel(category.Id, breadCrumbIds));
to just
categoryModel.SubCategories.AddRange(PrepareCategoryNavigationModel(category.Id, breadCrumbIds));
Single navigation cache fix
To make single navigation cache instead of making same cache for every single active category make change around line 1157
string cacheKey = string.Format(
ModelCacheEventConsumer.CATEGORY_NAVIGATION_MODEL_KEY,
_workContext.WorkingLanguage.Id,
string.Join(",", customerRolesIds),
_storeContext.CurrentStore.Id,
activeCategoryId);
to
string cacheKey = string.Format(
ModelCacheEventConsumer.CATEGORY_NAVIGATION_MODEL_KEY,
_workContext.WorkingLanguage.Id,
string.Join(",", customerRolesIds),
_storeContext.CurrentStore.Id,
0);
AND
var breadCrumb = activeCategory != null ?
activeCategory.GetCategoryBreadCrumb(categoryService, aclService, storeMappingService).Select(x => x.Id).ToList() : new List<int>();
to
var breadCrumb = new List<int>();
Note: Update-proof approach
For changes to persist when updating NopCommerce you can duplicate CatalogController.cs/CategoryNavigation as new controller in plugin. Then change views _ColumnsTwo, _ColumnsThree in theme to use this new controller. Or tell NopCommerce to add setting to switch between the two approaches :-P.