Mint: No SSH key-based login with encrypted home directory

The problem

We had a PC running Ubuntu 14.04 (with encrypted home folders), and OpenSSH.  We use key-based authentication on all our servers, and so we duly copied our public SSH key into ~/.ssh/authorized_keys.  However, the computer seemed to ignore this key!  Whenever we tried to SSH into the PC, we would be forced to enter a password.

After a bit of troubleshooting we realised that, if an SSH session was already established and the user opened a second session, the key-based authentication worked just fine!
What is happening?

More →