Caveat: You will need direct physical access to the machine, or an already functional ssh login (via password authentication or super-user key-pair).
In order to get this to work on my Debian box (my SSH host), I needed to generate a new key-pair (I used Putty on Windows 10; my SSH client), then ensure the following as already discussed by editing 'sshd_config':
$ sudo nano /etc/ssh/sshd_config
And putting these lines in, or uncommenting as required, and saving / write-out:
Then I needed to access the root account, so I issue:
$ sudo su
...and then make the necessary folders for ssh and a file for authorized_keys:
# cd /root
# mkdir .ssh
# cd .ssh
# nano authorized_keys
Then put the relevant public key in here, I pasted mine in from near the top of Putty-Gen, and save / write-out.
Then restart the sshd daemon, still as root, with:
# systemctl restart sshd
Then after I'd added the relevant .ppk file in my SSH Auth within Putty, it worked like a charm!
The key to this is that all users (root and other users) all share the same config in /etc/ssh/sshd_config, but they don't all share the same 'authorized_keys' files, so I needed to make root specific ones for this to work.
You can't simply add the public key generated for the root account in the /home/yournameuser/.ssh/authorized_keys file - it seems that the system doesn't look there for root access.