I have always run SELinux on Fedora/CentOS/RHEL and I don't remember a time where I had issues with authorized_keys. The only thing recently I recall about ssh is that is complains if the files in .ssh are not mode 600.
I'm not talking about RHEL4. I'm talking recent Fedoras (within the last year or 2). Making a brand new ~/.ssh/authorized_keys file has never worked for me without running restorecon (which is the thing I can never remember).
SELinux has come a long way since RHEL4 days.