You can try sshing in with maximum verbosity turned on to see why it fails:

A difference between a key and a password is that the user never gets a login/password prompt. The key is stored in a file which the ssh client knows where to get it. The key itself is a VERY long string of characters (a couple hundred I think). I think you can do preshared keys even if the client is DHCP, but someone else might know better about that.

On the point of locking out root login. On a Linux machine, root is the only user that is pretty much certain to exist. So, if root isn't available to a hacker, they have to guess both login and password.

(personal opinion follows)
All of it comes down to is which things you find useful in securing the system. Locking out root and alternate ports are the ones I find most useful.

me too.
i use a jumpbox. ssh requests can ONLY come from this box. you get to this box using RSA keyfob, so no password guessing here :)

from the jumpbox, ssh to any servers
no root logins allowed.
sudo access
preshared dsa keys

I disable root login, use passwordless login and use the allowusers directive to limit users.

Passwordless login uses a keypair. One key (the public key if I'm not mistaken) resides on the server; the other one (the private key) is on the the client machine(s) or you can carry it around on a memory stick. The private key is protected with a passphrase. An attacker needs both the private key and the passphrase to be able to get in.

PS I'm not that convinced of moving the port. A port scan will still reveal it as an open port. But that is my opinion and I might miss something.

point blank. but to be honest i never had any problems after moving the port. I guess it's them script kidies that do most of the probing. So moving the port is jut 90% safe. The skilled ones do it the other way anyways. Beside snort most of the time catches those port scans.

To be fool proof. Try something like portknocking to open up the SSH port.