Perhaps instead of (or in adition to) a prestige system that resets the characters, you could do a ‘new game +’ system where enemies have more health (probably ~+50% compared to the previous NG level) and have stronger and faster attacks (probably ~10% faster and 20% stronger), and possibly also something to make leveling harder/more difficult. For example, a static amount of weight (maybe one pound) stays behind when extracting weight and becomes permanent, stacking up as you remove weight, with the amount increasing every time you go to a higher NG+ level (i.e. one pound per extraction at NG+1, 2 at NG+2, 3 at NG+3, etc.). Alternatively (or in addition for a harder challenge), make it to where, in NG+1 and higher, extraction is only available if you complete the last level of a mission, so you can’t just go in and then exit back out to reduce everyone’s weight.
The benefits of going into NG+ would be getting higher weight amounts per run, due to the increase in enemy health, thus allowing for faster leveling. Also, the ability to go to the forum and brag about getting an S on Milk Dragon in NG+100 or some other such crazy thing. New upgrades for the items could also be given (so that they scale with the NG a little).
Going into a NG+ would be dependent on beating every stage in the game with at least an A (so you have all the items) and would be completely optional. Every NG level above one would require the same thing (to ensure you get all upgrades, if any), as every time you increase the NG level your times would be wiped.
Maybe I play too much Dark Souls, but this is the first thing I could think of for true longevity in this game.
EDIT: if you want the prestige system to allow for more powerful characters, you could make the NG+ system always reward one ‘prestige token’ every time a new NG+ level is started. That way players have to carefully choose which characters they prestige instead of just doing it to all of them every chance they get.