SSHd does not allow publickey authentication due to libcrypto bug
Actually, increasing the log level does not showed up anything related.
It only seems the client just jumped over the next possible key (DSA) which I have not got and then the method was dropped and password has been asked.
My client is a 14.04LTS, server is 16.04LTS.
The key was generated long time ago (by the time I was installed 14.04LTS).
The solution was to regenerate the RSA keys on the client and now it works as intended. Somehow the 16.04LTS is not backward compatible with the keys generated long time ago.