Reduce time to level 40?
In all honesty you should have the last skill you get, your elite unlock at 20, traits 15, utilities at 10 and weapon skills by 5. Other games have system like this in place because they are different and can get away with level gating, this game has only 3 utilities, 1 elite and weapon skills, you can’t level gate that and not introduce boredom/tediousness. Other games like I said are class level based, so each level bam something new for your class/level etc, this game simply was not built like that.
The real problem is newbies get lost apparently during leveling up for their personal story so incorporate something like this ..
http://i.imgur.com/V2PcneGl.png
problem solvededed! btw in a non intrusive or level gated way.
This makes it easier for new players to find things to do level up and makes alts for veterans less tedious.