Is your ping to the server high? The machine could be located far away from you. (Check your ping to the server with the "ping" command in the terminal/shell/command-line/command-prompt, not within Minecraft itself.)
Also, with "VPS hosting" there is a high chance that the company is oversubscribing machines. Check the virtualization technology in use and see if you can find info on if your host oversubscribes its machines.