The issue

I experienced a seemingly weird issue with a freshly installed CentOS server today.

SSH Public key authentication was correctly set up; The sshd_config was properly configured and a ~/.ssh/authorized_keys was present with the correct rights and verified correct contents (as the file was yanked from another, working, server with scp).

All attempts to connect to the machine using key authentication silently failed however.