Enquanto não sai o merge request, a atualização do nome da deploy key tem que ser direto no banco.
Numa instalação padrão, conectamos no banco pgsql via linha de comando:
su gitlab-psql /opt/gitlab/embedded/bin/psql --port 5432 -h /var/opt/gitlab/postgresql -d gitlabhq_production
 Depois localizamos o ID da chave (nesse caso eu exibi todas) e fazemos um update pelo id
SELECT id, title FROM keys WHERE type='DeployKey'; UPDATE keys SET title='root@shared-servers' WHERE id=181;
 Simples, não? =)