How to (re)support basement stair stringers?
Consider installing a pressure-treated 2x8 base plate onto the floor slab, underneath the stringers.  That's roughly how you'd build a new staircase by today's standards.

Notch the bottom of the stringers so the new base plate will fit.  This will be the trickiest part since you can't disassemble the staircase.
Slide the base plate into place.  It should be a tight fit requiring a little hammering or lifting of the stringers.
Fasten the base plate to the slab using your preferred concrete fasteners.
Fasten the stringers to the base plate using galvanized or stainless steel framing nails, or if not those, at least deck screws compatible with the PT lumber.

If you search for connect stair stringers to slab you can find a variety of drawings and photos that should be helpful.  The connections I suggest are more like the inner-stringer of a 3-or-more-stringer staircase, than then outsides.  That's due to using the base plate as a permanent shim.