Jickfoo -
When are your users experiencing the slowdown? For example, are you applying HostChecker policies to the realm, and users are waiting on HostChecker to complete before they are prompted for credentials? or, are they waiting between entering their credentials and the install/launch of the NC client?
I've got big problems with AD/LDAP authentication in 6.0Rx - but it always fails fast for me. You should be able to nail down Hostchecker problems with logging (watching the time on the dsHostChecker.log entries on the client) and authentication problems with a policy trace.
Good luck!