If you go to handgunlaw.us and bring up the NM file you will see a section re: places off-limits even with a permit/license.
In that section it says you may NOT carry open or concealed on tribal land, unless authorized by the tribe (which won't happen). NMSA 29-19-10.
HOWEVER, provided you stay on the bike or right by it if you're gassing up, you CAN legally carry concealed in NM. As long as you are on or in your vehicle you do not need a permit, if you are legal to possess. At 19 years old you are legal. If you are passing through on the public roadways you should be fine. Just don't go into any stores- stay right with the bike.
53 is a nice road, I was just on it a few weeks ago.