I think I would put a veneer on as suggested by JACK, but would then paint the stairs. Mine are white pine, which are also a soft wood, but they seem fine. Also if painting, the veneer could be a less expensive type instead of oak. Also paint is a lot more forgiving than stain. For example, you can fill and calk the gaps. I painted mine. They had carpet on them and when we pulled it off there were cracks, gaps, and even surface nails, in the top of the treads. I calked, filled, etc. and then painted them with two different colors. The treads are oil based porch and floor paint from Lowes. Here's how they turned out.