ssh keys for bitbucket.org can not be retrieved reliably

Since a few days ago some of our internal builds are failing due to an error that was quite hard to trace.
Our build script looks something like this:

1. Init git settings (username, email)
2. Get ssh-keys for both bitbucket.org and GitHub.com (ssh-keyscan -t rsa bitbucket.org)
3. Checkout code from Bitbucket

Now in 3. our builds would sometimes fail randomly saying "The authenticity of host 'bitbucket.org (...)' can't be established.".

When we were investigating this issue we've found out that ssh-keyscan -t rsa bitbucket.org doesn't get the key every time.
Instead sometimes it would simply return without any key at all:

Please make sure that your app servers actually return the ssh key so that we can use this (as documented here: https://confluence.atlassian.com/bitbucket/use-the-ssh-protocol-with-bitbucket-cloud-221449711.html) in our automated builds.

Thanks in advance!