SSH Authentication not working

SSH authentication not working anymore (Tested using two accounts. Windows, Mac | CMD, Terminal, Git Bash, Android Studio etc)

Details:

Existing working system stopped working few days ago. Creating new key pairs and adding to SSH keys in portal not working.

Technical:

ssh -T git@gitlab.com
ssh_exchange_identification: read: Operation timed out

ssh -Tvvv git@gitlab.com
debug1: Connecting to gitlab.com port 22.
debug1: Connection established.
debug1: identity file /Users/*username*/.ssh/id_ed25519-cert type -1
debug1: key_load_public: No such file or directory

It's nowhere mentioned that application specific password is required to use SSH keys.