MacBook taking long time to load the boot loader; rEFInd freezes
I'm assuming you're dealing with a Retina MacBook Pro.
If your Mac is taking that long to find something to boot and then also taking forever to boot afterwards then you may potentially have faulty storage.

Yes they probably will baulk at the 3rd party boot loader but as long as you have a backup you'll be OK. The Apple Store will run hardware tests to confirm whether or not the storage is faulty as well as reload the current version of OS X after wiping your storage.
It's part of their testing so if they can't load OS X cleanly then it's definitely a hardware issue.

You can find your local contact number here: https://support.apple.com/en-au/HT201232

On that note, why not just try cleanly installing OS X yourself after erasing your storage?

See http://osxdaily.com/2014/12/14/reinstall-os-x-mac-internet-recovery/

If you can do that successfully then you're just looking at an issue with rEFInd and/or your Linux partition (by the way why not just get Linux booting natively through EFI without the extra boot loader? http://heeris.id.au/2014/ubuntu-plus-mac-pure-efi-boot-short-version/)