Permission denied when connecting to an old server via SSH

Problem:
I couldn't connect to some old (poorly maintained TBH) server lately - while having all usual suspects like file permissions and key contents setup correctly on both sides:

  <username>@<server-ip>: Permission denied (publickey,password).

It was because my SSH client was up to date, but at the same time SSH service on the server wasn't updated for a long time. Even when trying to connect with older (visually longer) type of pair of keys (rsa) instead of newer one (ed25519) I was receiving same error.

Solution:
To the local SSH config file (typically found in: ~/.ssh/config) define alias to the given server - and within it include magic incantation: PubkeyAcceptedKeyTypes +ssh-rsa.

Example:

Host <server-ip>
  HostName <server-ip>
  User <username>
  PubkeyAuthentication yes
  PasswordAuthentication no
  PreferredAuthentications publickey
  PubkeyAcceptedKeyTypes +ssh-rsa
  IdentityFile <private-key>
  Port <port>

Solution originally found in some obscure Bitbucket docs.