I would suggest working through a proof-based linear algebra book in between to ease the transition. Axler's is a good one. Alternatives include Hoffman and Kunze and the more modern Friedberg, Insel, and Spence.
A lot of maths-related books, especially ones intended as textbooks will read like that in part because they aren't kidding about the 'abstract' in the title - they're trying to teach/re-summarize key concepts of mathematical abstraction. It's a good and true thing to notice.
That being said, Axler is an excellent book. I don't know if I would replace Strang with it, but I should add it as a supplement to the next edition of this guide!
Also enjoyed Artin's Algebra.
> solving problems is the only way to understand mathematics. There's no way around it.
...without also understanding that doing problems is not a substitute for understanding.
(I'm still salty about that course. I've been doing linear algebra based puzzles nearly every day of my life and this professor somehow made the topic a boring chore.)
I complained about this to a friend who had also taken the course and he turned me on to Axler. I read through the first chapter, nodding along as I went. I got to the problem questions and couldn't believe what Axler was asking was even related to the material I had read through. I really struggled at first to understand. Axler was heavily juxtaposed to my previous experience. However, when I did understand, I didn't just understand, I grokked.
It was just such an awesome experience, and I credit that book in particular with breaking me out of a mathematics plateau and with liberating my mathematics education from a strict reliance on academia. The text is almost magical.
I think this is a common first experience when first hitting pure mathematics. Mathematics often feels like very rote applications of rules drilled into one's mind, and then you hit a pure mathematics textbook and the questions become a step change in difficulty where you're expected to derive novel insights on your own that the text doesn't hold your hand in showing. A single problem can easily occupy days of your time before the "aha!" moment, but as you say, once you get the "aha!" you realize your understanding is quite profound as opposed to a shallower understanding of just how to apply a given set of rules.