I would definitely recommend water changes, at least every other day or even once a day depending on how high your levels are. How many frogs are in your 5 gal? Prime will help but the ammonia will sometimes still show up on the test because it's still there but has been rendered harmless. Water changes are your best bet. Your bio filter is what's going to neutralize the issue. Has your tank cycled? You might add ammonia chips to your filter if the problem continues. I've had luck with them. I also use compressed clay balls in my filter to add to my bio load (they are often used for aquaponics.)
Oh, and the prime will work on the nitrates and nitrites too so I wouldn't worry about using Nite-out.
More than 10 years
A frog tank, like a fish tank, needs to be cycled. If you are unaware of the nitrogen cycle just click the words and you'll be taken to an article explaining it.
I've never used Nite-Out but I believe some members have used it successfully. All I can recommend is to follow the directions closely, since many bactyeria additives are finicky.
I would recommend doing some water to get the ammonia and nitrite levels down as low as possible before adding Nite-Out.
One thing that concerns me, is your high nitrate levels. If you do not have nitrates in your tap water, the only way to get nitrates would be from the end result of the nitrogen cycle (ammonia-->nitrite-->nitrate). So if you do not have nitrates in your tap, that would seem to indicate that your filter does contain the bacteria that converts ammonia into nitrite and the bacteria that converts nitrite into nitrate, just not enough of those bacteria. This could be an indication that your filter is too small for the tank. It could be that there just isn't physically enough room in the filter media for enough bacteria to handle the entire bioload or that the filter just doesn't turn over the tank volume enough times per hour.