What does the load look like on your VPS at the time when you launch the install? Overall I find VPS slower than shared, semi-dedicated or dedicated so perhaps that's the issue but it still should not take more than a second or 2 not 10+

Have you looked at the network connection between you and the server/ Perhaps running a traceroute would reveal a problem.