If the stringers are compromised: Add a proper header or headers across the underside of your stringers to replace the support you had removed. Either that or replace the supporting wall. If it were just squeaking, there are other solutions, but obvious flexing is a safety problem that needs fixing.
If the stringers are not compromised, look for fasteners that aren't fully embedded. Start with the toenails at the top, I find they're usually the culprit. Remove and replace with a screw of the same diameter that is properly sunk.
When we talk about flex in a residential wood frame stair stringer, it is not out of the ordinary to see movement with the naked eye. However, if the flex is pronounced bowing, you have a problem. If it's the former case, simply a little movement, then you are likely getting worked up by a squeak that used to not be audible when the cavity below the stairs was walled off. Ripping the drywall off let the sound out. A key question is: are those stringers resting on top of the wall, or are they nailed to a rim board at the top (newer construction might have them hung in metal clips (hangers))?
- If no hangers and you want to delete the wall, remove the wall and add hangers at the center two stingers where you can access both sides, and then lag the stringers at the walls to the wall studs. Put a little dab of subfloor glue in the bottom of the saddle before pushing it up tight and nailing it off.
- If hangers are present and the stringers aren't flexing drastically, the wall is doing nothing and you are just hearing a loose fastener rubbing.
- If the stringers are bowing dramatically, add additional header material. I can't tell you what would be adequate in your case because that depends on a lot more than you've detailed here, but start with two 2x8 nailed together to be installed vertically (narrow edge top and bottom, wide side vertical), ripped across their top edge at an angle matching the slope of the stringers. You can either support them with 2x4 studs each end, or you can lag them to the studs at each side of the staircase. Either way, you can nail through the face of the beveled edge into the bottom of the stringers to provide some bracing, that really is not needed. Bracing for a stringer resists roll, and with the tops of stringers being braced by the treads and possibly the riser board, you would have to put enough weight on those stairs to break the stringers before they would flex down enough to roll for a standard slope length as this staircase is. (Bracing in a floor system improves stiffness by transferring point loads, dispersing the load to adjacent joists, this does not come into play with stringers).
- If a stringer is severed, and you still want to delete the remaining wall elements, you would sandwich the compromised stringer between new continuous full length 2x or simply cut a new stringer and sister it onto a damaged stringer.