Algebra rewards a procedure
Six years of school maths teaches that there is a correct sequence of steps and the job is to find it. That is a true description of almost everything a student meets before geometry, which is why it is such a hard habit to see from inside.
A proof asks for an argument
There is no sequence to find. There is a claim, and you build a case for it out of things already agreed. Most students have never been asked to do that in any subject, let alone in the one where they thought the answers were in the back.
Start away from geometry
I start with proofs about numbers — why two odd numbers always add to an even one. The geometry gets in the way of learning what a proof is, and a diagram gives a student somewhere to point instead of somewhere to argue.
Sentences before the two columns
Have them argue it out loud, in English, until it convinces somebody. The two-column form is a transcription of an argument, not a method for finding one, and students taught it as a method write beautiful columns that prove nothing.