I was in the same position as you recently (and still am to some degree) though in worse shape, since I decided I needed math at the end of college. The points people made previously about working at it and repetition are critical. I absolutely understand that you don't want to do things by rote, but what's important to realize is that like ANY other skill, there is one best way to improve, and it's called practice. You'll just need to do exercise after exercise, and read and re-read proofs, even when you don't feel that you "get" it. First you do it, then you'll get it.

The other thing that works the same for every other skill is to teach it. Get a friend who feels the same, and teach each other math. This works pretty well when you're not even talking to a real person, even. Just having to formulate your understanding solidly enough to convey it to someone else reveals where you get it and where you don't.

The personal trick that will help though I find is the hardest to do consistently is to be OK with not getting it. You'll spend a lot of time not understanding, so get comfortable with that fact and keep going. For myself, I tend to back off the subject when I don't get it right away, but I learn much faster when I stick with the stuff that makes me uncomfortable.

Prescriptively, try looking at How To Prove It for an explanation of what's going on in proofs, and how to engage with them.