Can't update/upgrade du to "Could not execute 'apt-key' to verify signature"
Changing the permission of /tmp back to their defaults worked for me:
sudo chmod 1777 /tmp
I had the same problem on my Ubuntu droplet at Digital Ocean (after a distro upgrade).
Just upgrade your kernel in the digital ocean administration site (yes, it's weird). There is a "kernel" option in the menu on the left side where you can select a new kernel image.
In my case the upgrade was from 3.x to 4.x series
In my case I played with AppArmor and enabled complain mode on sshd. Disabling it by aa-disable /usr/sbin/sshd and re-connecting fixed my problem.