Ubuntu server ssh after reboot: Permission denied (publickey)

I have a server setup where I can ssh to from my mac. The setup is made with a trusted key and it works perfect. But whenever I reboot the server and I that try to login using ssh my_user@ip then it says: Permission denied (publickey). However if I physically go to the server and log in as my_user, then suddenly I can get remote access by ssh from my mac as well. What do I need to change in my setup?

Well, the problem is that the key is stored in ~/.ssh/authorized_keys

With an encrypted home, you can not log in with the key as your home directory is encrytped.

Move authorized keys to somewhere else, I personally use /etc/ssh/.authorized_keys

You then edit /etc/ssh/sshd_config , add/edit the line

AuthorizedKeysFile /etc/ssh/.authorized_keys

Restart ssh server.

See also:

http://manpages.ubuntu.com/manpages/precise/en/man5/sshd_config.5.html