It's not just a born talent thing. Practicing interviewing and solving problems on a board in front of someone can do a lot to help you get over that anxiety. Yet most people never bother to practice and then wonder why they are bad at it.