Methods, apparatus, systems, and articles of manufacture are disclosed that determine a dynamic password update notification interval based on a breach risk classification and an automatic password update mechanism of an online service with which a user has an account. The disclosed methods, apparatus, systems, and articles of manufacture generate a password update suggestion and/or an automatic password update for the user at the dynamic password update notification interval determined by the processor circuitry.