Followed by this tutorial: https://www.digitalocean.com/community/tutorials/how-to-configure-secure-updates-and-installations-in-wordpress-on-ubuntu
I have a 64bit Debian 7 installed on my VPS(LEMP stack with php-fpm), this tutorial works well as long as I don't set passphrase to the generated ssh2 keys, with password I get error "Public and Private keys incorrect for user".
You might have better luck with https://wordpress.org/plugins/ssh-sftp-updater-support/ . The built-in Wordpress SFTP stuff uses libssh2, which doesn't work very well.
Like the OP, I followed the instructions and double/triple checked everything after receiving the same error.
Try looking at the SSH log (/var/ssh/auth.log) to get an idea of why it's not working. For me, it showed this error message and tipped me off to what was wrong:
Dec 28 06:04:23 onizuka sshd[17322]: User wp-user from 127.0.0.1 not allowed because not listed in AllowUsers
If you have SSH logins restricted to specific users (which I have done), you will need to add wp-user@127.0.0.1 to the AllowUsers definition in /etc/ssh/sshd_config and then restart the SSH daemon (or reboot server).
AllowUsers teranine wp-user@127.0.0.1
After doing this, installing themes and updates worked as expected within wordpress.