There are many, many ways that this question could possibly be answered. If, as you say, you are really comfortable with proofs, and you want a very rigorous approach, you might consider learning linear algebra from an actual "algebra" book instead of a "linear algebra" book. I think my mistake when (re)-learning linear algebra is not taking this route. Not all "algebra" books have good coverage of linear algebra though some that do include:
- Rotman's Advanced Modern Algebra
- Artin's Algebra
- Adkins and Weintraub's Algebra: An Approach via Module Theory
All of these books are readable and have very good coverage of linear algebra. Of course, if you go this route, you will end up learning more standard algebra topics than just "linear algebra". One could argue though that such standard topics are needed anyway. Consider, for example, the standard definition of the determinant via the classical combinatorial formula. To really make sense of this and to work with it effectively you need to know about permutation groups and various facts about permutations such as every permutation can be expressed as a product of transpositions. These facts really are needed in linear algebra but most linear algebra books don't explain them thoroughly. On the other hand, every good algebra book will.
On the other hand, if you want something that is theoretically sound but more elementary and/or computationally oriented, you might consider one of these:
- Kwak and Hong's Linear Algebra
- Meyer's Matrix Analysis and Applied Linear Algebra
Both of these texts are very readable and have a good mixture of theory/application. One thing nice about Meyer's book for self-study is that complete solutions are provided for the exercises. Also, all of the above books can be used profitably together though don't expect the same topics to be treated the same way.