I found a better proof for a theorem than a proof from a published paper. Is it possible for me to publish my proof with the same theorem citing that paper?
Why wouldn't it be? This is somewhat common. To cite just one example, Dilworth's Theorem (about antichains in a partially ordered set) originally had a somewhat involved proof when it was first published in 1950. Since then there have been a number of papers published with titles like "A Proof of Dilworth's Chain Decomposition Theorem" (that one by Fred Galvin), with many of these papers being widely cited in their own right. The one by Galvin is a masterpiece of mathematical elegance.
The crucial question is if you can convince the referees that your proof is both sufficiently new and sufficiently better and/or interesting so as to warrant publication.
Sure. People publish new proofs of old results all the time. I've done it twice, myself.
Publishability, as with any paper, depends on how much you can get people to care about your new proof. If the result itself isn't very significant, your proof will need to be a big improvement; for a more significant result, it might be enough to improve one of the steps. People will probably care more if your proof is shorter, simpler, requires less material from outside the field (or, conversely, establishes links with other areas), leads to a stronger result, etc.
Be careful that your new proof isn't circular. If Smith proves that every widget has an even number of facets and Jones extends this to prove that the number of facets is actually a multiple of six, you don't get to publish A Short Proof of Smith's Theorem that simply points out that every multiple of six is even.
As several people already mentioned, the prime number theorem is a great example:
No elementary proof of the prime number theorem is known, and one may ask whether it is reasonable to expect one. Now we know that the theorem is roughly equivalent to a theorem about an analytic function, the theorem that Riemann’s zeta function has no roots on a certain line. A proof of such a theorem, not fundamentally dependent on the theory of functions, seems to me extraordinarily unlikely. It is rash to assert that a mathematical theorem cannot be proved in a particular way; but one thing seems quite clear. We have certain views about the logic of the theory; we think that some theorems, as we say ‘lie deep’ and others nearer to the surface. If anyone produces an elementary proof of the prime number theorem, he will show that these views are wrong, that the subject does not hang together in the way we have supposed, and that it is time for the books to be cast aside and for the theory to be rewritten.” - Hardy, 1921
Then, Erdös and Selberg gave a non-complex-analysis proof in 1948, see history of this problem here.
Apart from the trivial answer, yes, I would like to highlight a few points before submitting new proof for an existing theorem to a publishing venue.
- It depends on where you are submitting it. Certain peer-reviewed journals might not welcome proofs for established theorems.
- It mainly depends on the subject or discipline of concern. It is much more common to see alternate proofs in venues of mathematics and physics than in computer science.
- It depends on whether the new proof is theoretical or practical in nature. Unless the theorem is not practically proved before, referees of reputable technical publications might not readily accept application papers of existing theorems.
- The new proof ought not to be a trivial simplification of an existing proof. Otherwise, it would become an exposition paper than a research paper. This again comes down to the perception of the reviewer and the publisher.
Having stated above, you could technically publish anything new as long as you believe it benefits a wide scientific community.