Всем выражаю большую благодарность за помощь, каждый совет однозначно помог.
Решение оказалось как всегда на поверхности.
Все дело было в том, что файл sshd_config на сервере, который находится по следующему пути: /etc/ssh в строчке AllowUsers содержал всего одного доступного пользователя, добавил пользователя git, под которым происходит авторизация и все стало работать.
Строка AllowUsers после внесения изменений стал выглядеть вот так:
AllowUsers youruser git

Расписываю алгоритм более подробно, на случай если кто-то столкнется с такой проблемой.

1. Открываем файл sshd_config на сервере, который находится по следующему пути /etc/ssh
   
2. Ищем строку AllowUsers, скорее всего там будет прописан ваш пользователь под которым обычно происходит авторизация по SSH. Добавляем через пробел пользователя git и строка получается вот такой: AllowUsers youruser git
   Сохраняем изменения
   
   
3. Перезагружаем sshd командой: sudo /etc/init.d/ssh restart
   
4. Получаем ключ для Gitlab, много где описано как это сделать, я сделал следующим образом:
   Вводим команду на локальной машине, с которой будете работать:
   ssh-keygen -t rsa -f ~/.ssh/gitlab
   После переходим в папку .ssh и копируем ключ из файла gitlab.pub, идем в веб-интерфейс gitlab и войдя под нужным пользователем добавляем ему ключ.
   
5. Теперь создадим файл config на локальной машине в папке .ssh, он нужен, чтобы указать какой ключ для какого соединения применять, так как подключение на сервер у нас происходит тоже по SSH.
   Данный файл получился вот такого содержания:
   

   Host 45.80.69.169
       IdentityFile /home/kramdmitriy/.ssh/id_rsa
       port 22
   Host gitlab.iso-team.ru
       IdentityFile /home/kramdmitriy/.ssh/gitlab
       port 22

   
   Первый ключ - это ключ для сервера, второй для гитлаба.
   Сохраняем файл и пробуем подключиться к gitlab по SSH