漏れたパスワードは、そのサービスへの不正ログインと、同じパスワードを使っている他のサービスへの不正ログイン（パスワードリスト攻撃）に使われるおそれがあります。通知を受けたら、そのサービスと、同じパスワードを使っていたすべてのサービスでパスワードを変更してください。
「暗号化されていた」場合は安全？
多くのサービスは、パスワードをそのまま保存せず、元に戻せない形（ハッシュ値）に変換して保存しています。この場合、漏れたデータから元のパスワードをすぐに知ることは難しくなります。ただし、
- 短い・単純なパスワードは、総当たりや辞書で元のパスワードを割り出されることがある
- 保存方法が古い・弱いと、解析されやすい
このため、ハッシュ化されていた場合でも変更するのが安全です。
変更の優先順位
- 漏れたサービスそのもの
- 同じパスワード（または似たパスワード）を使っているメールアカウント
- お金が動くサービス（通販・決済・銀行）
- SNSなどその他
順番の考え方はパスワードを変える順番で詳しく説明しています。