Once you do that, login to GitLab with your credentials.
On the upper right corner, click on your avatar and go to your Profile settings.
Navigate to the SSH keys tab.
Paste your public key that you generated in the first step in the 'Key' box.
Optionally, give it a descriptive title so that you can recognize it in the event you add multiple keys.
Finally, click on Add key to add it to GitLab. You will be able to see its fingerprint, its title and creation date.
Note: Once you add a key, you cannot edit it, only remove it. In case the paste didn't work, you will have to remove the offending key and re-add it.
Congratulations! You are now ready to use Git over SSH, instead of Git over HTTP!