Analysing the problem
There are two places an ssh connection can go wrong, on the server or at the client. We want to rule them out one at a time.
On the Server
To increase the logging on the server set the following line in your /etc/ssh/sshd_config file;
There's also a DEBUG2 and DEBUG3 to get even more information sent to the logs.
To monitor the logs, use the command tail -f /var/log/auth.log
On the Client
You can add verbosity to your client connection with a -v option.
ssh -v firstname.lastname@example.org
There is also a -vv and -vvv to increase the verbosity of the output
Spotting the Error
Set your log monitoring going on the server with the above command and then try connecting to it from the client using a verbosity level also above. Now, carefully check the outputs from each and look for could not's, Permission denied's, no such identity:'s or Incorrect RSA1 identifier's etc. These are most likely the problem if your in a similar position to me.
Permissions - Client Side
The certificates and known_hosts (usually found within ~.ssh) all need to be readable by the user. In the simplest instant, id_rsa, id_rsa.pub and knwon_hosts should be owned by and in your user group and should be readable by the user, below is the 'default' setup.
-rw------- username username id_rsa
-rw-r--r-- username username id_rsa.pub
-rw-r--r-- username username known_hosts
Permissions - Server Side
Again, the certificates and this time the authorized_keys files must be readable by the user being logged in. Defaults as shown below:
-rw------- username username authorized_keys
-rw-r--r-- username username id_rsa
SSH on the server needs to be able to see/read the authorized_keys file and associated server certificates; therefore if they are on an encrypted device then a session must be live for the device to be readable by the daemon. This is often seen when you can login via password and whilst that session is live, you can then login via authorised keys and no password.