Mavericks update broke ssh key-based authentication
Turns out it was about the key file name.

authorized_keys2 was the correct one to use for SSH2 keys a loooong time ago when I first configured the key-based authentication. For years, authorized_keys2 file was deprecated but still working. In Mavericks version of opensshd the support has been dropped.

This can be fixed with a simple rename:

cd ~/.ssh; mv authorized_keys2 authorized_keys