Если у пакета B в рекомендуемых зависимостях указан пакет A - то apt-mark
Если не указан - то apt-mark поможет, но ближайший autoremove предложит этот пакет удалить.
Как вариант, можно собрать пустой meta-пакет, который будет для себя требовать A и B. Тогда при удалении B этот мета-пакет будет удалён по зависимостям, а A - останется никому не нужным и будет предложен к удалению autoremove.