If I rederived a result (oblivious that it already existed), should I cite the original paper?

Citation has multiple purposes, as described by several answers on this site (e.g. 1, 2). Broadly speaking, those purposes mostly fall into three classes: giving a trustworthy source, giving credit, or suggesting further reading. Any individual citation might serve several of these purposes, or only one of them. So when you cite a paper, that doesn't necessarily make it seem like you took the result from there; you might simply be giving credit to the first person(s) to publish the result, or referencing an external source to back up what you're saying.

What this means for your case is that you should definitely cite the other paper. The exact wording you use to do so depends on several factors, including whether you think an explicit statement of the result, and/or your derivation of it, are still worth including in your paper - for example, if you think your derivation is more clear, or relaxes some assumptions of the original, or so on. Here are some possibilities along the lines of what I've used or read:

• "This result was originally derived in reference [1]." (possibly in a footnote)
• "For a more detailed derivation, see reference [1]."
• "Here I present an alternate derivation of the result in reference [1]."
• "(statement of result) [1]. In brief, this can be derived as follows: ..."
• "This uses the result that (brief statement of result) [1]." (probably in a footnote)

and so on. Or you can just cite it without comment, and unless the conventions of your field are otherwise, people won't necessarily assume that you took the result from the other paper. (Nor will they even care, in most cases.)

I will write from the perspective of mathematics. This sort of issue comes up often and can often be tricky. One thing is clear: you must cite the prior work. Now you write:

If I cite the original work it will seem like I simply took it from there,

I don't follow. First of all, you can say "I proved X independently, before I became aware of the work of [CITE]." Whether you will get any credit for this is another matter, but you can certainly say it.

But moreover, assuming the literature you found is old enough so that your work really was done afterwards and not at roughly the same time [in mathematics this is usually the case with published literature, since the publication process is rather slow], the only point of mentioning the result is if your take on it is not completely subsumed by the original. If there is some novelty in your approach to the result, it is fine to include result...and your new derivation of it. (Comment on @Massimo Ortolano's answer: in mathematics, appendices rarely contain omitted proofs from the body of the article.)

Let me reiterate that it often happens that after you've written a math paper you find out that there's some amount of overlap with past work. You don't necessarily have to scrap the whole thing or even excise all parts of your paper that overlap with past work -- in some cases, doing this would make your paper less readable with no other benefit. However, you should make a strong effort to do justice to the previous work. (It does not feel good to have a finished paper in hand and learn that X% of it is not new. If I'm being really honest, I often do feel a momentary temptation not to include an "obscure" citation that could lower the perceived value of my work. I've never given into it though, and at this point I recognize it as pure ephemeral evil and it passes through me quickly.) The right way to look at it is this: if no one cares about this part of your article, then no one cares and you have nothing to gain by omitting the citation. If they do care, then the readers who care / know the most will know about the other work -- either immediately or eventually -- and you place yourself in a much better situation by calling attention to the overlap yourself.

The purpose of publishing a paper is not to massage your ego, nor to gain credit for your work - although these are useful side benefits - it is to contribute to the global body of knowledge about whatever subject you are publishing on. You should consider this in deciding whether to include the derivation.

If there is nothing novel or original about your derivation then you serve your subject and your audience better by omitting it entirely and simply using the result and referring them to the paper you have now discovered for the derivation.

If there is something about your new derivation worth mentioning, then you should include it but also cite the earlier paper and indicate what it is about your new derivation that makes it worth mentioning.

Either way you should cite the earlier paper. How you came up with the idea is largely irrelevant.