Oh,
Anastasia is fabulous. Everything from its sound to its meaning is wonderful. As for nns... I'd go with
Annie or Stasia (STAY-zha) since I prn it the English way. You could go with Stasi (STAH-zee). That's fairly cool and sounds almost Russian to my ears.
Stacey would also work as a nn if you want something that's more English.