I like the idea of a currency requirement similar to that for IFR or landing currency for flying with passengers. (As an instrument pilot, if you haven't done certain tasks (approaches and holds) in the last 6 months, you aren't legal for IFR flight.) We might require power-on and power-off stalls be logged every 90 days. This wouldn't be like the BFR, which requires an instructor. You could do it solo.
The really interesting question is whether you limit this to piston singles, because there are a lot of professional pilots who never get recurrent stick and rudder training. Find someone who flies a King Air or a PC-12 for a living and ask when they last did stalls in that aircraft. The landing and IFR currency requirements don't bother professional flying operations, because those requirements usually get covered through regular flying or can be accomplished effectively in a sim. This would require people to actually practice something not encountered in normal flight. (Gasp.)
This is a NASA produced video about ice induced stalls. If you saw a NASA video on the topic previously, that one was made in 2009 and is superseded by the advice in this video. It's almost 30 minutes, but if you fly a FIKI equipped aircraft, this is very much worth your time to get the latest NASA advice on stall management in icing conditions. (If you don't fly a FIKI equipped aircraft, stay the hell away from visible moisture near the freezing level.)
My biggest takeaway was how attentive you have to be to detecting an impending stall. You'll be level, at full power, well above your stall speed, with no stall warning horn sounding. The stall may feel like turbulence--particularly if you're already in turbulence. When it comes, you better lower that nose or they're going to need DNA analysis to identify your remains.