My first advice is to not play mage right now, the meta is minion heavy, you can't possibly remove them all. You can't draw well with mage, your deck probably has a lot of RNG too which will be inconsistent, you want consistency to climb. Tempo mage style can't ever have board control, mech mage is better but if you draw bad, you can't do much. You need to play something that likely curves very well.
The ladder is full of paladins of all kinds that can fill the board very cheaply and quickly, you flamestrike that? I don't care, here is another murloc knight. You need to contest the board against those. You need 2 drops that deal with minibot, juggler and muster. Mana wyrm is a good 1 drop but it's not enough.
Playing something like hybrid or mid range hunter works quite well, or you can just play paladin too. It's pretty cheap. Overall you need to increase your game knowledge to climb, that is to know how every class functions, what are their game plan, how they can kill you next turn etc. For that you have to play all classes and know their cards and guess what your opponent has in the hand by their actions.
You don't even need many legendary cards to climb to 5 or legend even. Dr. Boom is enough, Loatheb is good too right now. Most of those big guy legendary cards can't ever meet the board as the game is set before then.
For anyone who has been playing this game for a while and know how it works, it's very easy to play it, there are not that much variables you can control here. board state? well of course you need that and it's really easy with paladin to have a favorable board for MC. The deck is easy as in there are plenty of room for errors in it, as your opponent can easily misplay on secret turn and you deal so much damage then for little effort.