While I adore both names (Ezra is my current top boys name, Asa is on the short list) saying them together like that I realize that yeah they are way too similar and sing song for brothers and especially twins. I hadn't realized before but now I know I wouldn't use the two.
I'd go for another unusual biblical name to compliment like Ezra and Boaz, or Asa and Zimri.