We immediately redirect the user to Facebook. If we were to display a message first, it would take even longer.
Some things you may want to try are disabling any social profile plugins you may have enabled. During authentication, the social profile plugins will make connections to Facebook to download profile data and the user's image. I don't think this is the cause since it sounds like the delay is when you're on the facebook.com site doing the authentication, but it's worth trying.
Beyond that, generally check your system and user plugins to see if there any you don't need enabled. Any of those could be slowing down the login process as well, which are good to disable in general unless needed.
To note, I just tested on your site. My initial registration did take about 10-15 seconds. After logging out, when I tried again, it was less than 2-3 seconds.
Thanks,
Alex