Can stainless steel replace titanium for Mach 3+ speeds?
Both the MiG-25 and MiG-31 designs had engines that would overheat and be damaged an anything past Mach 2.83, so both planes were limited by this. Typical speeds were closer to Mach 2.5 to extend the life of the planes. The highest aerodynamic heating occurs at the leading edges. It's possible that the MiG designs used titanium in these areas but opted for steel in most other areas, which was cheaper and easier to work with. This would have allowed the aircraft to reach speeds closer to the SR-71, even if the engines couldn't keep up.

The SR-71 was designed to cruise at up to Mach 3.3 at 80000ft, a similar altitude to the MiGs. Atmospheric heating is related to the cube of the speed. Mach 3.3 generates 10% more heat than Mach 3.2, and the SR-71 reached at least Mach 3.5. It seems the SR-71 flew faster and higher than the MiGs.

Heat is only one consideration though. Another big issue is weight. Steel is generally much heavier than a comparable structure made from titanium. The SR-71 empty weight was about 40% higher than the MiG-31, but the MTOW was 70% higher. This allows much more payload for mission equipment, but also fuel. The MiGs were designed to fly relatively short range interception or reconnaissance missions, having unrefueled ranges of 2000km or less. The MiG-31 could fly 3000km but only with drop tanks. The SR-71 was designed as a long range reconnaissance aircraft, and had a range of 5400km which enabled it to fly long missions over enemy territory.

Another consideration is size. The SR-71 was a larger plane than either the MiG-25 or MiG-31. It had a wingspan of 17m, compared to 14m of the MiGs, and a length of 33m, compared to 20m and 23m for the MiGs. This means higher forces on the aircraft structure.