Yours is a common case of huge workflows. I suggest you to read the Aaron Labiosa 's posts about this subject >>> Defensive Workflow Design Part 3 - Separation of Concerns
The basic suggestion is to make subworkflow/subroutines/child workflows
The architectural reason this is happening is that the SharePoint Workflow Engine must cache all workflows on their first run. This can even happen after an application pool recycle in IIS. If the workflow is running for the first time since a recycle, SharePoint will attempt to cache the workflow again. Since Nintex is a solution that manipulates the SharePoint workflow engine to do amazing things, Nintex is also held by some(keyword) limitations within SharePoint. There isn't much you can do about this fact. But as Fernando points out, making your workflows smaller can effect the time it takes to cache the workflows. So there is opportunity to limit the caching affects.
Thanks for the best share and clear information.