It is partially my fault for having so many styles, but still. It was painful enough that I went into debugging the code, and then I saw the rebuildMaxExecution variable, I keep looking at it for some time and then asked myself, "was that always there?"
I guess not. I assume it was introduced to prevent timeouts (a good thing), and in the process made the whole thing much more slower. It pains me to see my CPU at 0.3% usage, no active db queries, and yet the Cache Rebuild takes forever ....
Well, I updated it to 300, and everything started going a lot faster
I do not recommend this to everyone, though, if you do that, also adjust the max_execution_time on php.ini and for nginx users the fastcgi_read_timeout