So what would be the best way to learn to be efficient in magic ? Are the few tutorials still the way to go ? (last time I checked them out some keyboard shortcuts seemed not to work, I guess changed since then)

In my experience, the tutorials are good to get a general idea on what you can do. I suggest getting to know the commands in any case (see http://opencircuitdesign.com/magic/userguide.html) then you can do

macro help

to check the current keybindings or modify them, etc.