主要は ssh のホストルールの設定が多すぎて、正確なマッチングが設定されていないため、複数の鍵が存在することも相まって、ssh が一つずつ試行し、成功するマッチングを試みる前に、失敗回数が多すぎてサーバーに拒否されてしまいました。
解決策:ホストマッチングルールに正確なマッチングを追加します。
# ~/.ssh/config
Host gitlab.xxx.com
HostName gitlab.xxx.com
User root
IdentityFile ~/.ssh/other_rsa
# 以下の行を追加して、対応する鍵を正確にマッチング
IdentitiesOnly yes
# かつ、プロキシを使用しない
IdentityAgent none
# GitHub
Host github.com
# 443 ポート用
HostName ssh.github.com
User git
Port 443
IdentityFile ~/.ssh/viki_rsa
IdentitiesOnly yes
Host *
User root
IdentityFile ~/.ssh/viki_rsa
PreferredAuthentications publickey
IdentityAgent "xxx"