I remember reading somewhere that a mathematician, faced with a new question, will alternate looking for a proof on Monday, Wednesday, and Friday, with looking for a counterexample on Tuesday, Thursday, and Saturday. Sunday: just relax and let the subconscious go to work.
There are famous cases of conjectures that turned out to be wrong, contrary to widespread expectations. Also false “proofs” whose flaws remained undetected for decades.
So the “intuition” you’re seeking, while not totally mythical, isn’t nearly as sure footed as you might think.
Anyway, I do have two pieces of advice.
First, it sounds like you always go for the proof, without even looking for a counterexample. Follow the model of the first paragraph. Like any other skill, this will improve with practice.
Second, alternation has a second benefit, besides keeping your options open. If you get stuck somewhere in the middle of a proof, analyzing the obstacle will often suggest a key aspect of a counterexample. Conversely, if you can’t get all the parts of a counterexample to fit together, pondering why may provide hints towards a proof.
Here's an example from real analysis. (Historically significant, too.) Suppose you're asked to prove or disprove: the limit of a convergent sequence of continuous functions with domain $[0,1]$ is continuous.
Thinking informally, I might say, "OK, let $f_n\to f$ and let $c\in[0,1]$. I want to force $|f(x)-f(c)|$ to be small by making $|x-c|$ small. Well, since each $f_n$ is continuous, I can make $|f_n(x)-f_n(c)|$ small. And since $f_n\to f$, I can make $|f_n(x)-f(x)|$ and $|f_n(c)-f(c)|$ both small by making $n$ large. So it looks like I have the ingredients for a so-called $\epsilon/3$ proof."
When I start trying to write out the proof in detail (the usual "$\forall\epsilon\exists\delta$" jazz), if I'm careful I run into a problem. I've been given an $\epsilon$. I want $n>N$ to imply that both $|f_n(x)-f(x)|$ and $|f_n(c)-f(c)|$ are less than $\epsilon/3$, for all $|x-c|<\delta$. Both $N$ and $\delta$ are under my control. Since $f_n\to f$, I'll have an $N_0$ that works for $|f_n(c)-f(c)|$, but for $|f_n(x)-f(x)|$, the $N$ will depend on $x$. Say $n>N_x$ implies $|f_n(x)-f(x)|<\epsilon/3$. Is there some maximum value of $N_x$ that will work for all $|x-c|<\delta$?
Well, maybe not! Now I have an obstacle in my "proof". Can I turn this into a counterexample? As $x$ gets closer and closer to $c$, I want $N_x$ to get unboundedly bigger.
At this point I start playing around. I have a rough idea of what I want the $f_n$'s to look like. I sketch some graphs with $c=1$. I decide to have $f_n(x)\to 0$ for $x<1$, but $f_n(1)\to 1$. For $x$ very close to 1, I want $f_n(x)$ to stay close to 1 until $n$ gets very big. Eventually I hit on the idea of letting $f_n(x)=x^n$. And there's my counterexample.
The history: Cauchy, famous for a higher level of rigor than most of his predecessors, "proved" this false theorem. (Well, actually something equivalent for convergent series.) You'll find the whole story in Jeremy Gray's The Real and the Complex: A History of Analysis in the 19th Century, chapter 4. (The actual historical details are way more complicated than this $x^n$ example.)
