I really like it. The first time I heard it, it did strike me as feminine, but I figured it had some masculine history. I think going with
Alexander, nn
Sasha is the best way, because 1) It gives him something to "fall back on" in case he doesn't like
Sasha, or is teased because of it (especially since
Alexander has a lot of nicknames, and the full version itself); and 2) Like you, I prefer formal names over nicknames as full titles.
(Oh, and my nine-year-old brother would like to say that he thinks
Sasha on a boy is good, too. :) )