I had similar problem, see [Solved] Upgrade from 6.12.65-20 to 6.12.65-23 now very slow
I had to open up TCP port 11371 outgoing from the server, this is used to access the PGP servers. So check you can resolve DNS lookups and allow that port outgoing. I went from about 5 minutes reload time down to 20 seconds.