Добрый день. Склоняюсь к тому, что не нужно. На сайте ФНС (предпоследний вопрос) отвечают, что замена необходима при изменении сведений, хранящихся в КСКПЭП. А в 63-ФЗ адрес регистрации упоминается только для ЮЛ:
Цитата (Ст. 14 63-ФЗ):2. Сертификат ключа проверки электронной подписи должен содержать следующую информацию: 1) уникальный номер сертификата ключа проверки электронной подписи, даты начала и окончания срока действия такого сертификата; 2) фамилия, имя и отчество (если имеется) - для физических лиц, наименование и место нахождения - для юридических лиц или иная информация, позволяющая идентифицировать владельца сертификата ключа проверки электронной подписи;