For some script a passwordless SSH login was required. However, despite the public key had no passphrase set, a password was being asked nevertheless.

The SSH client is not really verbose on what was going on, but it turned out to be the private key's permissions. When the permissions are too open, SSH refuses to use that key and falls back to something else. So make sure that they key has mode 600 (read and write only for the owner of the key) and that the owner is OK.