SSIS package deployment. Changing protection level takes a very long time
It seems that I solved my own problem. I do not know exactly what cause it, but here is what i did.

It turns out that only one of the projects that we have had the problem I described. That project happened to have multiple packages included. For testing I removed all packages from the project and added one at the time, built the project after each step and tested the deployment. They all worked fine individually and ultimately I ended up with a project with all packages that deploys fast. 

This got me thinking that maybe the project file/build files got hosed somehow and they all needed a full refresh/rebuild.