This is our workflow for rebase:
And after this the history is still not linear, we end up with multiple branches "guitar-hero" like.
Any ideas what we are doing wrong?
What you're seeing are merge commits. These track the action of merging the feature branch into the target branch.
GitLab by default uses a normal merge, which produces merge commits. If you don't want merge commits, you need to perform a fast-forward merge. GitLab supports this: Fast-forward merge requests | GitLab
Retain a linear Git history and a way to accept merge requests without creating merge commits.
With that said, I would encourage you to not use this fast-forward workflow, and appreciate the merge commits.