diff --git a/openssh-8.7p1-negotiate-supported-algs.patch b/openssh-8.7p1-negotiate-supported-algs.patch
new file mode 100644
index 0000000..2fb9297
--- /dev/null
+++ b/openssh-8.7p1-negotiate-supported-algs.patch
@@ -0,0 +1,63 @@
+diff --color -rup a/regress/hostkey-agent.sh b/regress/hostkey-agent.sh
+--- a/regress/hostkey-agent.sh	2021-08-20 06:03:49.000000000 +0200
++++ b/regress/hostkey-agent.sh	2022-07-14 11:58:12.172786060 +0200
+@@ -13,8 +13,12 @@ r=$?
+ grep -vi 'hostkey' $OBJ/sshd_proxy > $OBJ/sshd_proxy.orig
+ echo "HostKeyAgent $SSH_AUTH_SOCK" >> $OBJ/sshd_proxy.orig
+ 
++PUBKEY_ACCEPTED_ALGOS=`$SSH -G "example.com" | \
++    grep -i "PubkeyAcceptedAlgorithms" | cut -d ' ' -f2- | tr "," "|"`
++SSH_ACCEPTED_KEYTYPES=`echo "$SSH_KEYTYPES" | egrep "$PUBKEY_ACCEPTED_ALGOS"`
++
+ trace "load hostkeys"
+-for k in $SSH_KEYTYPES ; do
++for k in $SSH_ACCEPTED_KEYTYPES ; do
+ 	${SSHKEYGEN} -qt $k -f $OBJ/agent-key.$k -N '' || fatal "ssh-keygen $k"
+ 	(
+ 		printf 'localhost-with-alias,127.0.0.1,::1 '
+@@ -31,7 +35,7 @@ cp $OBJ/known_hosts.orig $OBJ/known_host
+ unset SSH_AUTH_SOCK
+ 
+ for ps in yes; do
+-	for k in $SSH_KEYTYPES ; do
++	for k in $SSH_ACCEPTED_KEYTYPES ; do
+ 		verbose "key type $k privsep=$ps"
+ 		cp $OBJ/sshd_proxy.orig $OBJ/sshd_proxy
+ 		echo "UsePrivilegeSeparation $ps" >> $OBJ/sshd_proxy
+diff --color -rup a/sshconnect2.c b/sshconnect2.c
+--- a/sshconnect2.c	2022-07-14 10:10:07.262975710 +0200
++++ b/sshconnect2.c	2022-07-14 10:10:32.068452067 +0200
+@@ -222,6 +222,7 @@ ssh_kex2(struct ssh *ssh, char *host, st
+ {
+ 	char *myproposal[PROPOSAL_MAX] = { KEX_CLIENT };
+ 	char *s, *all_key;
++	char *hostkeyalgs = NULL, *pkalg = NULL;
+ 	char *prop_kex = NULL, *prop_enc = NULL, *prop_hostkey = NULL;
+ 	int r, use_known_hosts_order = 0;
+ 
+@@ -264,14 +265,19 @@ ssh_kex2(struct ssh *ssh, char *host, st
+ 	    myproposal[PROPOSAL_MAC_ALGS_STOC] = options.macs;
+ 	if (use_known_hosts_order) {
+ 		/* Query known_hosts and prefer algorithms that appear there */
+-		myproposal[PROPOSAL_SERVER_HOST_KEY_ALGS] = prop_hostkey =
+-		    compat_pkalg_proposal(ssh,
+-		    order_hostkeyalgs(host, hostaddr, port, cinfo));
++		if ((hostkeyalgs = order_hostkeyalgs(host, hostaddr, port, cinfo)) == NULL)
++			fatal_f("order_hostkeyalgs");
++		pkalg = match_filter_allowlist(hostkeyalgs, options.pubkey_accepted_algos);
++		free(hostkeyalgs);
+ 	} else {
+-		/* Use specified HostkeyAlgorithms exactly */
+-		myproposal[PROPOSAL_SERVER_HOST_KEY_ALGS] = prop_hostkey =
+-		    compat_pkalg_proposal(ssh, options.hostkeyalgorithms);
++		/* Use specified HostkeyAlgorithms */
++		pkalg = match_filter_allowlist(options.hostkeyalgorithms, options.pubkey_accepted_algos);
+ 	}
++	if (pkalg == NULL)
++		fatal_f("match_filter_allowlist");
++	myproposal[PROPOSAL_SERVER_HOST_KEY_ALGS] = prop_hostkey =
++	    compat_pkalg_proposal(ssh, pkalg);
++	free(pkalg);
+ 
+ #if defined(GSSAPI) && defined(WITH_OPENSSL)
+ 	if (options.gss_keyex) {
diff --git a/openssh.spec b/openssh.spec
index 5627a63..6f41f0a 100644
--- a/openssh.spec
+++ b/openssh.spec
@@ -51,7 +51,7 @@
 
 # Do not forget to bump pam_ssh_agent_auth release if you rewind the main package release to 1
 %global openssh_ver 8.7p1
-%global openssh_rel 15
+%global openssh_rel 16
 %global pam_ssh_agent_ver 0.10.4
 %global pam_ssh_agent_rel 4
 
@@ -246,6 +246,10 @@ Patch1004: openssh-8.7p1-gssapi-auth.patch
 # d9dbb5d9a0326e252d3c7bc13beb9c2434f59409
 # fdb1d58d0d3888b042e5a500f6ce524486aaf782
 Patch1005: openssh-8.7p1-host-based-auth.patch
+# Don't propose disallowed algorithms during hostkey negotiation
+# upstream MR:
+# https://github.com/openssh/openssh-portable/pull/323
+Patch1006: openssh-8.7p1-negotiate-supported-algs.patch
 
 License: BSD
 Requires: /sbin/nologin
@@ -440,6 +444,7 @@ popd
 %patch1003 -p1 -b .mem-leak
 %patch1004 -p1 -b .gssapi-auth
 %patch1005 -p1 -b .host-based-auth
+%patch1006 -p1 -b .negotiate-supported-algs
 
 %patch100 -p1 -b .coverity
 
@@ -720,6 +725,10 @@ test -f %{sysconfig_anaconda} && \
 %endif
 
 %changelog
+* Thu Jul 14 2022 Zoltan Fridrich <zfridric@redhat.com> - 8.7p1-16
+- Don't propose disallowed algorithms during hostkey negotiation
+  Resolves: rhbz#2068423
+
 * Thu Jul 14 2022 Dmitry Belyavskiy <dbelyavs@redhat.com> - 8.7p1-15
 - Disable ed25519 and ed25519-sk keys in FIPS mode
   Related: rhbz#2087915