One thing to do is to separate deploy to pre-deploy, deploy, and post-deploy. Even then we should look into what takes so long. I just did a deploy to staging and it took 30 minutes (but there were 50 users online).