If you say
GIT_SSH_COMMAND="ssh -v" git clone ...
you’d supposedly be shown what’s the issue.
Given the “freshly installed” it might the case that you’re transferring from an older LTS-type distribution? When I recently did from Mint I found that the newer Manjaro SSH had deprecated some older-type RSA keys due to vulnerabilities. You can in the case of github supposedly just generate and use a different keypair which I’d suggest – but if this is the issue and you really, really can’t, you can re-enable those older-type RSA keys with in /etc/ssh/ssh_config:
HostkeyAlgorithms +ssh-rsa
PubkeyAcceptedAlgorithms +ssh-rsa
An at this time even older issue might be
KexAlgorithms +diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
But don’t as said do any of that if you can just generate a new keypair, and of course, this while assuming it’s the problem in the first place; see initial ssh -v advise frst.