As this was a new server, initially I thought perhaps I had something wrong in the configuration, but when I tried to connect manually using
ssh -vvv <host>
to give the full verbose output of the connection attempt I noticed something interesting.
debug1: Skipping ssh-dss key /home/rcheesley/.ssh/my_key - not in PubkeyAcceptedKeyTypes
That's a new one on me!
After a bit of searching around, I came across a few sources which suggested that with OpenSSH 7 and above, DSA keys are being blocked by default.
Support for ssh-dss, ssh-dss-cert-* host and user keys is disabled by default at run-time. These may be re-enabled using the instructions at http://www.openssh.com/legacy.html
There are many reasons for this move, but it does mean anybody using DSA keys will either need to apply the instructions above, and ideally regenerate keys.
As Ubuntu 16.04 ships with OpenSSH 7.2p2 this meant that I needed to apply the workarounds (setting PubkeyAcceptedKeyTypes=+ssh-dss in my SSH config) and set about updating all my DSA keys. Fun and games!