One thing to watch out for is that if a board is notched, and say you leave 6 inches uncut, it's not necessarily as strong as a 6-inch board, and I believe boards need to be re-rated after they are cut because of knots and such. In this case, for this reason, if you sister on a 6-inch board you would more than double the strength.
The minimum for load rating doesn't necessarily give a nice firm staircase anyway. If you go well above that minimum, the stairs will feel nice and rigid.
Vertical support posts in the middle would help a lot too (if that's an option.)
Because of a stair program I wrote, I've talked to hundreds of stair builders and I've come across a couple that used engineered 3x12's but glued a 2x3 on the top (where the treads were going to be cut out. This left more uncut stringer, while most of the 2x3 is cut away anyway. An excellent glue-job would be necessary though.
Yet another option is to not cut the notches all the way in, and partially support the treads with brackets. For example, you are using 11.5 inch treads. Only cut the notchces (run) in, say, 6 inches. Now you have 5.5 inches of overhang, and this is supported by brackets or boards. This is sort of a hybrid between box and notched, and leaves more of the stringer for span support, but you have to spend more time attaching and supporting the treads because they are no longer just happily sitting on the notch.
Stair Stringer Calculator --