"Invalid locale" in Debian

I need some advice or hints to solve a problem on a Debian system.

On a relatively freshly installed Linux (Debian 12.2);
when I run in the terminal one of these commands:

# aptitude search some-package
# aptitude -s install some-package
# aptitude install some-package

I get this message:

Warning: Invalid locale (please review locale settings, this might lead to problems later):
locale::facet::_S_create_c_locale name not valid

I assume I should do something about it.

I did some research but did not find any clear answer.

For instance I installed locales-all, as suggested in some post I saw on SOF, but it didn't change anything.

What is the best way to handle this issue ?

As a matter of facts, down the road as a result of running this command:

# aptitude install postgresql

I see the following (which seems to be related to the issue above):

.......
Fetched 41.6 MB in 7s (6343 kB/s)...

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
LANGUAGE = "en_US:en",
LC_ALL = (unset),
LC_CTYPE = "UTF-8",
LANG = "en_US.UTF-8"
are supported and installed on your system.
perl: warning: Falling back to a fallback locale ("en_US.UTF-8").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory
Preconfiguring packages ...
.......

Some more information that could be related to my issue.

This is what happens when I run the locale command:

# locale
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory
LANG=en_US.UTF-8
LANGUAGE=en_US:en
LC_CTYPE=UTF-8
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=
#

These are the contents of /etc/default/locale and /etc/environment

# cat /etc/default/locale
# File generated by update-locale
LANG=en_US.UTF-8
LANGUAGE="en_US:en"
# cat /etc/environment
#

/etc/environment is empty.

One more thing I should say is that in order to use Japanese input.
I installed these packages: ibus, ibus-mozc. I had some hard time to make it work and it is possible that I messed up some locale settings a that point.

Any relevant tip by someone used to these problems will be much appreciated.