If you're naming a Russian character, you should be aware that Russians don't have middle names like we usually think of them.
Anastasia would have a patronymic middle name, her father's first name with the suffix eva or evna on it. For example, the Grand Duchess
Anastasia Romanov was
Anastasia Nicolaev(n)a Romanov.
If you're just having fun,
Anastasia Mari(n)a is nice and Russian flavored.
Not fond of
Nadia, has an unpleasant sound.