I have an issue with being unable to create a “linear” history for my branch using rebase.

I may have a wrong concept as to what can/should be done, but this is what am working with:

---A---B---E   master
       |
       |---C---D  feature

At this point both branches (master and feature) are synced with their remote counterparts, meaning that both the local and remote repositories have these commits. At this point I ran:

git checkout feature
git pull --rebase origin master

at this point, since rebase is local not remote, before I can git push i have to git pull (and i think herein lies the main issue).
So a git pull and git push later and what I expected was the following:

---A---B---E---C'---D'---MergeCommit---

But instead I end up with:

---A---B--------------------C---D---MergeCommit---
       |                 |
       |---E---C'---D'---|

Note: I am not sure if the C and C' are correctly placed, as i have no way of telling which of these two was the original and which is a “copy” but there are two of them present.

You can see the picture bellow to make it more clear.

Now, I do not mind having two “lines” here, for the lack of a better word.
I do not mind having a “merge commit”. All of this is fine.
What drives me crazy is the duplicating of commit C and commit D.

Or even the following would be still be acceptable:

---A---B-------------------MergeCommit---
       |                 |
       |---E---C'---D'---|

How do I get rid of them, on either of the “lines”. I keep saying lines because all of this is a single branch. I’ve not dabbled with version control for a few years now, i am pretty sure this was not the behavior back when I did, and i didnt have duplicated commits, instead they were a single linear graph. I would blame git pull because of the message that i get now, which i do not recognize, Merge made by the 'ort' strategy. this seems new to me and i feel like it is the reason for the issues.