Indeed, Anastasia, most Greek surnames ending with "-akis" are form Crete. The ending "-akis" in first names is diminutive. So, what Johnny is to John, Yannakis is to Yanni. George Dubya, for example, is not-so-affectionately known as "Georgaki" in Greeca, as opposed to his dad George. The word you mention Anastasia, is "paidaki" (little child) as opposed to "paidi" (child).
PS: So much for the manlines of your GGL friend's name, Magia :P No self-respecting Greek male would continue calling himself "Little John" beyond the age of 13 :).