It was taking the guts of 10 seconds for the password prompt to appear whenever I tried to SSH into the server.
I found that this was caused by some sort of reverse DNS lookup being done on my host.
Arsebiscuits to that!
Make sure that GSSAPIAuthentication is set to no as follows in /etc/ssh/sshd_config:
GSSAPIAuthentication noThen restart your sshd service.