I have had a young adult male axolotl (Smaug) for about a year now. Recently when testing water parameters I have found that the nitrate levels are very high (80ppm), but both nitrite and ammonia levels are at 0. I currently do a 20% water change once a week. Should I perhaps increase this to every 3 days until I can get the nitrate levels down?
Water changes will indeed reduce nitrate levels within your tank and with 80ppm you'll definitely want to reduce that as soon as you can.
You could increase the percentage of your water changes, but one thing that I've found has helped a lot is growing a plant such as pothos (formally referred to as Pothos aureus, also commonly known as devil's ivy) in the top of the tank with the roots trailing into the tank. It grows extremely quickly and has helped keep my nitrate levels much more manageable. Planted tanks in general help to keep the levels down, but if that's not possible, I'd definitely recommend giving pothos a try. This technique is commonly called 'aquaponics'.
This is a fantastic video explaining the process: https://www.youtube.com/watch?v=RcDoh0NcXLU
P.S. What a great name for an axolotl!
Test your tap water for nitrates to be sure that isn't contributing to your problem. And yes, more frequent water changes can help with keeping nitrate levels down. The addition of ghost shrimp can also help, but they may not last long as axolotls tend to find them very tasty.
I have a similar issue in my tank (high nitrates, close to 0 ammonia/nitrites). To solve this, I performed a 70-80% water change. After a few days I did a 30% change. Then monitored it and now do ~25% change after levels start creeping close to 40ppm.