I agree with pan64. There could be a password checker in place to verify the strength of the password when entering a new password. Many places do that, and it seems to be relatively simple.

In fact, if you are signing in on line to a government web site they often have rules about the password strength, length, and expiration as well as preventing reuse of the same password for a certain number of times. My bank does the same.

It should not be difficult to put something of that nature in place for passwords on the servers and then just verifying it is in place and working would meet the security checklist requirements. Seems like it would be a wrapper around or replacement of the passwd command on the server and probably already exists somewhere.

It should work for all users since many on a server may have sudo access and their user password would need to be as secure as the root password.

I do not know if any encrypted record or file is generated that can show any indication of it.

At my job, we still have the policies on the complexity of passwords. But like I told you, when I asked for some root passwords I almost went flat on my back.

It seems like a good idea to have a tool that evaluates the complexity of the password at the beginning of 'creating' it, but when we already have an infrastructure with more than 4k servers it is more complex.

I wanted to do a quieter job and audit the server from my side but it looks like I will have to audit the keys directly with the corresponding area.

with more than 4k servers you must have an automated way to install/configure that tool.
Checking those passwords directly/manually is insecure, unreliable, not really acceptable by audits and also not really feasible on 4k servers. But you know.