Yasuo does in general deal pretty well against squishy melee's; because of his mobility. However, I am more inclined to think you misplayed. Badly. It might be because you don't know the champion well, but lets take a look.
Let's say at level 3 yasuo has 2 points in Q and one in E. 2 Q's, an E, ignite, and maybe even an auto gives yasuo a total of 200+70+110+60=460 respectively. Yea, its a rough calculation; i didn't account for items on either side, nor did I bring runes or masteries into it. But with a base health of 744, this combo isn't "two shoting" anything. In fact, I have you more than the 2 shot, and it is a little more than half. So no, yasuo cannot do what you are suggesting.
Now, I don't necessarily think Rek'sai auto loses the lane, but I haven't played the matchup, so this is just hypothetical for me. But it seems to me that if you see Yasuo dash in under tower, you should burrow and land a knockup. That will ensure at least one tower hit. Finally, rek'sai has phenomenal wave clear and should be able to clear waves fairly easily. You also have the ability to gap open instantly with E. You can pop his shield with burrowed Q and you should be able to out sustain him.
It might not be a phenomenal lane, but there are certainly things that you can try. And if it exists that yasuo just crushes rek'sai, it kinda just is what it is. There are lots of champions that completely crush other champions, it certainly wouldn't be a first.