Case closed, this was due to a hard-to-recognize typo in the key given to me. Thank you and sorry for bothering.
- F-Multi
ssh-rsa 1024 0d:fa:ed:f3:b4:bO:79:41:1f:25:6b:58:36:19:97:73
1024
is not the problem.
521
is not a typo.