How big is your tank? The smaller the tank, the more quickly the nitrite concentrations will build up.
We have a thread, which might help you:
http/www.fishforums.net/index.php?/topic/433778-rescuing-a-fish-in-cycle-gone-wild-part-il/
But, at this point the best answer is to get the nitrite DOWN and keep it down. First, 25% water changes are worthless when dealing with 5ppm nitrite. First, that's the highest reading on the test kit, and the value could be significantly higher than that. But, assuming that the 5ppm is accurate, a 25% water change would merely lower it to 3.75ppm, which is still toxic and will quickly build up again. But, if the reading were actually 6 or even 7 ppm in reality, the test would not get under 4.5ppm even immediately after the water change.
Safe Start
can be helpful, but only if its properly handled from manufacturing to when you used it. But even so, I'd never trust it with fish, I'd always do a fishless cycle to 'test' it first.
But, ultimately, you are in a tough spot. The fish are likely suffering from nitrite poisoning - which affects the ability of the fish to take oxygen into their blood (the nitrite actually builds up in their red blood cells, turning them brown, and blocking their ability to hold oxygen). The only thing that will allow the fish to eliminate that nitrite from their blood is to get them into water without nitrite... and they can slowly recover from the problem. They also need extra oxygen in the water, so increasing surface agitation, will be a great benefit.
LARGE water changes and LOTS of them, will keep your fish healthy... but not help your cycle that much. Salt will keep nitrite from ENTERING the fish (as described in the article linked above) but won't allow the fish to expel the nitrite that is already built up in their blood, if nitrite is still present in the water. But, salt will allow the nitrite to sit in the tank, so that the bacteria can build up and deal with it.
There are a few ways to go... Personally, the best way for you to go would be to do a MASSIVE water change... change every bit of the water that you can... ALL of it. Remove all the nitrite that you possibly can. It might help to remove the fish to a small container to suck up ALL the water that you can, and then replace the fish after refilling the tank. Then, add a LOT of floating plants to the tank. Keep the lights on the tank for 12-16 hours a day. The floating plants are some of the best options for removing nitrogen from the water and they will take the nitrogen as ammonia produced by the fish. They won't be able to take it all, but they can take a lot, and the more they take, the less nitrite will be produced by the bacteria. (1 ppm ammonia - on an API test kit - converts to 2.7 ppm nitrite - on an API test kit - so every 1 ppm taken up by the plants of ammonium can have a dramatic effect on the speed - or lack thereof - with which nitrite will build up.)
And having a little nitrite in the tank, will allow the bacteria to continue to build up to deal with the rest. Funny thing is that the floating plants will also grow rapidly, and take up more ammonia leading to even less nitrite...
Floating plants like hornwort, duckweed (which can be hard to get rid of later), frogbit, water lettuce, etc. are some of the options available to you. This won't get take up all the ammonia, and so nitrite will continue to build up, but at a slower rate, as less ammonia will be available to convert to nitrite.
Keep an eye on the ammonia and nitrite levels daily. If the levels are starting to build up... do a massive water change to drop them again.
As for Stability, and other products like it - yes, they are not very good.
As for adding bacteria in a product like Safe Start, where you have very high nitrite - yes, it can kill them.