Sastasha opens up after you have done the envoy misson, and then have gone from there to the Drowning Wench in Limsa Lominsa Upper Decks.

It is part of the main story, and you cannot unlock it until you get to that point. Speed leveling will not help.