Just adding a comment here that may help debugging this issue.

While working on https://pagure.io/SSSD/sssd/issue/3602 I've noticed that the first lookup may fail as we don't talk directly to the DP in order to get up-to-date data.

There was a patch (together with the series that ended up merged as part of 3602) which forced us to talk to the DP as the first thing (similar to what we do with PAM) and always get up-to-date info from the DP ... however, Sumit noticed it caused some noticeable delays compared to what we currently have.

So, sorry for jumping in and adding information which is not exactly useful for solving this issue, but I hope that it at least helps a little bit.

@fidencio, I think your assumption is right. From the logs I would say that the user is already in the cache and the ssh responder uses cached data without the recently added ssh key.

A failed password based authentication will force a cache update which explains why it works after the failed attempt.

I had a brief talk with @sbose about this issue on SSSD channel and here goes his suggestion:

<fidencio> sbose: around? about https://pagure.io/SSSD/sssd/issue/3669 ... as we
           should *not* take the path of contacting the DP on every single request,
            what would be your suggestion? IIRC cache_req would do this for us for
           free (check the cached data, in case it's no updated, contact the DP and
           get updated data ...)
<sbose> fidencio, either an option to switch the behavior on and off, maybe with an
        extra timeout like pam_id_timeout. E.g. ssh_key_timeout, if the option is
        not set or larger equal entry_cache_user_timeout we have the current
        behavior, if it is set to 0 the DP in contacted all the time. And a time in
        between means that the ssh responder will update the entry after the
        given time.

Thank you for taking time to submit this request for SSSD. Unfortunately this issue was not given priority and the team lacks the capacity to work on it at this time.

Given that we are unable to fulfill this request I am closing the issue as wontfix.

If the issue still persist on recent SSSD you can request re-consideration of this decision by reopening this issue. Please provide additional technical details about its importance to you.

Thank you for understanding.

SSSD is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in SSSD's github repository.

This issue has been cloned to Github and is available here:
- https://github.com/SSSD/sssd/issues/4688

If you want to receive further updates on the issue, please navigate to the github issue
and click on subscribe button.

Thank you for understanding. We apologize for all inconvenience.