All those proofs only make things more complicated
I think you're half right and half wrong. Needless to say, it depends on who is learning it. For people who know how to read proofs, they can actually make things simpler because they can extract the intuition of how things work from the proofs (or more likely by thinking about things on their own). Without that understanding of why things work, the subject can be really meaningless and forgettable. Applications are good, but if you are just learning by rote and taking things on faith, you'll forget it all in 2 seconds.
Really, there should be books that cut out the middle man, that is the proof, and just explain the ideas behind the proofs directly for those who are not adept at reading the proofs (and really, sometimes, even for many of them, because although they will still get most of the intuition if they know what they are doing, it may be filtered and watered down from the overly formal presentation). I'm not aware of a book that really does that consistently for linear algebra (but I'm only familiar with a few of the books). Tends to be either proofs or too much mindless plugging and chugging. I'm working on my own notes for linear algebra that I plan to make available eventually, but it has been slow going because I am too busy with other things. I might try to make videos on put them on youtube or recruit someone else to do the dirty work of writing it up, but eventually, I'll find a way.
Also, it isn't just a matter of reading proofs, even if you know how to do that well. It helps to do problems and examples, along with the proofs--sometimes that will clear the way for understanding the proofs.
Strang got me started, but I really started to understand linear algebra when I took more advanced math classes like real analysis.
