Нашел решение и оно очень простое!
Для депроя основного проекта на сервер я добавил публичный ключ Deploy keys в настройках.
Так вот, нужно было включить этот ключ в настройках КАЖДОГО приватного репозитория, который находится в зависимостях composer.json.
Private repo > Settings > Repository > Deploy keys > Privately accessible deploy keys > Enable (ключ из основного проекта)
https://docs.gitlab.com/ee/user/project/deploy_key... 
